An application of Tutte’s Theorem to 1-factorization of regular graphs of high degree |
| |
Authors: | David Cariolaro Anthony JW Hilton |
| |
Institution: | a Institute of Mathematics, Academia Sinica, Nankang, Taipei, 11529, Taiwan b School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, UK |
| |
Abstract: | A well known conjecture in graph theory states that every regular graph of even order 2n and degree λ(2n), where λ≥1/2, is 1-factorizable. Chetwynd and Hilton A.G. Chetwynd, A.J.W. Hilton, 1-factorizing regular graphs of high degree — An improved bound, Discrete Math. 75 (1989) 103-112] and, independently, Niessen and Volkmann T. Niessen, L. Volkmann, Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree, J. Graph Theory (2) 14 (1990) 225-246] proved the above conjecture under the assumption that . Since these results were published no significant or even partial improvement has been made in terms of lowering the bound on λ. We shall obtain here a partial improvement on λ. Specifically, using the original Chetwynd-Hilton approach and Tutte’s 1-Factor Theorem, we show that the above bound can be improved to , apart (possibly) from two families of exceptional cases. We then show, under the stronger assumption that λ≥λ∗≈0.785, that one of the two families of exceptional cases cannot occur. |
| |
Keywords: | 1-factorization 1-factorization conjecture Tutte&rsquo s 1-factor theorem |
本文献已被 ScienceDirect 等数据库收录! |
|