|
|||||
|
|
A note on 2-factors with two components |
|
| Authors: | Ralph J. Faudree Ronald J. Gould Michael S. Jacobson Linda Lesniak Akira Saito |
| Affiliation: | aDepartment of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, USA bDepartment of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA cDepartment of Mathematics, University of Colorado at Denver, Denver, CO 80127, USA dDepartment of Mathematics and Computer Science, Drew University, Madison, NJ 07940, USA eDepartment of Computer Science, Nihon University, Sakurajosui 3–25–40, Setagaya-Ku, Tokyo 156-8550, Japan |
| Abstract: | In this note, we consider a minimum degree condition for a hamiltonian graph to have a 2-factor with two components. Let G be a graph of order n3. Dirac's theorem says that if the minimum degree of G is at least , then G has a hamiltonian cycle. Furthermore, Brandt et al. [J. Graph Theory 24 (1997) 165–173] proved that if n8, then G has a 2-factor with two components. Both theorems are sharp and there are infinitely many graphs G of odd order and minimum degree which have no 2-factor. However, if hamiltonicity is assumed, we can relax the minimum degree condition for the existence of a 2-factor with two components. We prove in this note that a hamiltonian graph of order n6 and minimum degree at least has a 2-factor with two components. |
| Keywords: | Hamiltonian cycle 2-factor Minimum degree |
| 本文献已被 ScienceDirect 等数据库收录！ | |