3‐Factor‐Criticality of Vertex‐Transitive Graphs |
| |
Authors: | Heping Zhang Wuyang Sun |
| |
Affiliation: | School of Mathematics and Statistics, Lanzhou University, Lanzhou, P. R. China |
| |
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. |
| |
Keywords: | vertex‐transitive graph factor‐criticality matching connectivity 05C70 |
|
|