Premium
3‐Factor‐Criticality of Vertex‐Transitive Graphs
Author(s) -
Zhang Heping,
Sun Wuyang
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21873
Subject(s) - combinatorics , mathematics , cograph , discrete mathematics , indifference graph , vertex transitive graph , symmetric graph , chordal graph , pathwidth , 1 planar graph , transitive relation , vertex (graph theory) , line graph , graph , voltage graph
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.