3‐Factor‐Criticality of Vertex‐Transitive Graphs. Issue 3 (9th April 2015)

• Record Type: Journal Article
• Authors: Zhang, Heping; Sun, Wuyang
• Is Part Of: Journal of graph theory. Volume 81:Issue 3(2016)
• Page Start: 262
• Page End: 271
• Publication Date: 2015-04-09
• Subjects: vertex‐transitive graph -- factor‐criticality -- matching -- connectivity -- 05C70; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21873
• Languages: English
• ISSNs: 0364-9024

Abstract

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 nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.