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

Authors: Sizhong Zhou

Abstract:

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 .

Keywords: graph, minimum degree, neighborhood, [a, b]-factor, Hamiltonian [a, b]-factor.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1075426

References:

[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.