3-factor-criticality of vertex-transitive graphs

DOI10.1002/JGT.21873MaRDI QIDQ2800542zbMATH OpenOpenAlexFDO

Authors Heping Zhang, Wuyang Sun

Publication date 15 April 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.3940

zbMATH Keywords

matchingconnectivityvertex-transitive graphfactor-criticality

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A graph of order $n$ is $p$-factor-critical, where $p$ is an integer of the same parity as $n$, if the removal of any set of $p$ vertices results in a graph with a perfect matching. 1-Factor-critical graphs and 2-factor-critical graphs are factor-critical graphs and bicritical graphs, respectively. It is well known that every connected vertex-transitive graph of odd order is factor-critical and every connected non-bipartite vertex-transitive graph of even order is bicritical. In this paper, we show that a simple connected vertex-transitive graph of odd order at least 5 is 3-factor-critical if and only if it is not a cycle.

Recommendations

• 4-factor-criticality of vertex-transitive graphs
• \(p\)-factor-criticality of vertex-transitive graphs with large girth.
• 3-factor-criticality in domination critical graphs
• On \(k\)-factor-critical graphs
• The characterization of \(p\)-factor-critical graphs

Cites work

• scientific article; zbMATH DE number 1545446 (Why is no real title available?)
• scientific article; zbMATH DE number 238423 (Why is no real title available?)
• scientific article; zbMATH DE number 3211575 (Why is no real title available?)
• scientific article; zbMATH DE number 5052357 (Why is no real title available?)
• Connectivity of transitive graphs
• Extendability and factor-criticality
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• On \(k\)-factor-critical graphs
• On cyclic edge-connectivity of transitive graphs
• On n-extendable graphs
• On the structure of factorizable graphs
• Small separations in vertex-transitive graphs
• Super restricted edge-connectivity of vertex-transitive graphs

Cited in

(3)

• 4-factor-criticality of vertex-transitive graphs
• \(p\)-factor-criticality of vertex-transitive graphs with large girth.
• Some sufficient conditions for a graph with minimum degree to be \(k\)-factor-critical

This page was built for publication: 3-factor-criticality of vertex-transitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800542)