3-factor-criticality of vertex-transitive graphs

DOI10.1002/JGT.21873zbMATH Open1333.05249arXiv1212.3940OpenAlexW1606974704MaRDI QIDQ2800542FDOQ2800542

Authors: Heping Zhang, Wuyang Sun 

Publication date: 15 April 2016

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

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.

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

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

zbMATH Keywords

matchingconnectivityvertex-transitive graphfactor-criticality

Mathematics Subject Classification ID

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

Cites Work

• On n-extendable graphs
• Super restricted edge-connectivity of vertex-transitive graphs
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• Connectivity of transitive graphs
• On \(k\)-factor-critical graphs
• Title not available (Why is that?)
• On cyclic edge-connectivity of transitive graphs
• Title not available (Why is that?)
• Extendability and factor-criticality
• Title not available (Why is that?)
• On the structure of factorizable graphs
• Title not available (Why is that?)
• Small separations in 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)