Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653542 | European Journal of Combinatorics | 2014 | 11 Pages |
In 1985, Bollobás, Saito and Wormald characterized all triples (t,d,k)(t,d,k) such that every tt-edge-connected dd-regular graph has a kk-factor. An interesting research question is to ask when a tt-edge-connected dd-regular graph has a kk-factor, if the triple (t,d,k)(t,d,k) does not satisfy the characterization. The problem was solved by Niessen and Randerath in 1998 in terms of a condition involving the number of vertices of the graph.In this paper, we continue the investigation of the problem from a spectral perspective. We prove that, for a tt-edge-connected dd-regular graph GG with (t,d,k)(t,d,k) violating the characterization of Bollobás et al., if a certain eigenvalue, whichever depends on (t,d,k)(t,d,k), is not too large (also depends on (t,d,k)(t,d,k)), then GG still has a kk-factor. We also provide sufficient eigenvalue conditions for a tt-edge-connected dd-regular graph to be kk-critical and factor-critical, respectively. Our results extend the characterization of Bollobás, Saito and Wormald, the results of Cioabă, Gregory and Haemers, the results of O and Cioabă, and the results of Lu.