A Sufficient Condition for Graphs to Have Hamiltonian [a, b]-Factors

Let a and b be nonnegative integers with 2 ≤ a < b, and
let G be a Hamiltonian graph of order n with n ≥ (a+b−4)(a+b−2)
b−2 .
An [a, b]-factor F of G is called a Hamiltonian [a, b]-factor if F
contains a Hamiltonian cycle. In this paper, it is proved that G has a
Hamiltonian [a, b]-factor if |NG(X)| > (a−1)n+|X|−1
a+b−3 for every nonempty
independent subset X of V (G) and δ(G) > (a−1)n+a+b−4
a+b−3 .

• Sizhong Zhou

• graph
• minimum degree
• neighborhood
• [a
• b]-factor
• Hamiltonian [a
• b]-factor.

[1] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, The
Macmillan Press, London, 1976.
[2] J. R. Correa, M. Matamala, Some remarks about factors of graphs, Journal
of Graph Theory 57(2008), 265-274.
[3] S. Zhou, Independence number, connectivity and (a, b, k)-critical graphs,
Discrete Mathematics 309(12)(2009), 4144-4148..
[4] S. Zhou, A sufficient condition for a graph to be an (a, b, k)-critical
graph, International Journal of Computer Mathematics, to appear.
[5] S. Zhou, J. Jiang, Notes on the binding numbers for (a, b, k)-critical
graphs, Bulletin of the Australian Mathematical Society 76(2)(2007),
307-314.
[6] S. Zhou, Y. Xu, Neighborhoods of independent sets for (a, b, k)-critical
graphs, Bulletin of the Australian Mathematical Society 77(2)(2008),
277-283.
[7] H. Matsuda, Fan-type results for the existence of [a, b]-factors, Discrete
Mathematics 306(2006), 688-693.
[8] Y. Gao, G. Li, X. Li, Degree condition for the existence of a k-factor
containing a given Hamiltonian cycle, Discrete Mathematics 309(2009),
2373-2381.
[9] H. Matsuda, Degree conditions for Hamiltonian graphs to have [a, b]-
factors containing a given Hamiltonian cycle, Discrete Mathematics
280(2004), 241-250.
[10] S. Zhou, B. Pu, Hamiltonian factors in Hamiltonian graphs, International
Journal of Computational and Mathematical Sciences 3(2)(2009), 83-85.
[11] G. Liu, L. Zhang, Factors and factorizations of graphs (in Chinese),
Advances in Mathematics 29(2000), 289-296.
[12] L. Lovasz, Subgraphs with prescribed valencies, Journal of Combinatorial
Theory 8(1970), 391-416.