A Sufficient Condition for Graphs to Have Hamiltonian [a, b]-Factors
Authors: Sizhong Zhou
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 .
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1075426Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1073
 J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, The Macmillan Press, London, 1976.
 J. R. Correa, M. Matamala, Some remarks about factors of graphs, Journal of Graph Theory 57(2008), 265-274.
 S. Zhou, Independence number, connectivity and (a, b, k)-critical graphs, Discrete Mathematics 309(12)(2009), 4144-4148..
 S. Zhou, A sufficient condition for a graph to be an (a, b, k)-critical graph, International Journal of Computer Mathematics, to appear.
 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.
 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.
 H. Matsuda, Fan-type results for the existence of
[a, b]-factors, Discrete Mathematics 306(2006), 688-693.
 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.
 H. Matsuda, Degree conditions for Hamiltonian graphs to have
[a, b]- factors containing a given Hamiltonian cycle, Discrete Mathematics 280(2004), 241-250.
 S. Zhou, B. Pu, Hamiltonian factors in Hamiltonian graphs, International Journal of Computational and Mathematical Sciences 3(2)(2009), 83-85.
 G. Liu, L. Zhang, Factors and factorizations of graphs (in Chinese), Advances in Mathematics 29(2000), 289-296.
 L. Lovasz, Subgraphs with prescribed valencies, Journal of Combinatorial Theory 8(1970), 391-416.