Hamiltonian Factors in Hamiltonian Graphs

Authors: Sizhong Zhou, Bingyuan Pu

Abstract:

Let G be a Hamiltonian graph. A factor F of G is called a Hamiltonian factor if F contains a Hamiltonian cycle. In this paper, two sufficient conditions are given, which are two neighborhood conditions for a Hamiltonian graph G to have a Hamiltonian factor.

Keywords: graph, neighborhood, factor, Hamiltonian factor.

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

References:

[1] B. Alspach, K. Heinrich, G. Liu, Contemporary design theory-A collection of surveys, Wiley, New York, 1992, 13-37.
[2] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, The Macmillan Press, London, 1976.
[3] J. R. Correa, M. Matamala, Some remarks about factors of graphs, Journal of Graph Theory 57(2008), 265-274.
[4] M. Kano, A sufficient condition for a graph to have
[a, b]-factors, Graphs and Combinatorics 6(1990), 245-251.
[5] S. Zhou, Independence number, connectivity and (a, b, k)-critical graphs, Discrete Mathematics, Available online 15 January 2009.
[6] S. Zhou, A sufficient condition for a graph to be an (a, b, k)-critical graph, International Journal of Computer Mathematics, to appear.
[7] 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.
[8] 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.
[9] H. Matsuda, On 2-edge-connected
[a, b]-factors of graphs with Ore-type condition, Discrete Mathematics 296(2005), 225-234.
[10] S. Zhou, H. Liu, Y. Xu, A degree condition for graphs to have connected (g, f)-factors, Bulletin of the Iranian Mathematical Society 35(1)(2009), 1-11.
[11] G. Li, Y. Xu, C. Chen, Z. Liu, On connected (g, f+1)-factors in graphs, Combinatorica 25(4)(2005), 393-405.
[12] H. Matsuda, Degree conditions for Hamiltonian graphs to have
[a, b]- factors containing a given Hamiltonian cycle, Discrete Mathematics 280(2004), 241-250.
[13] J. Cai, G. Liu, Binding number and Hamiltonian (g, f)-factors in graphs, Journal of Applied Mathematics and Computing 25(2007), 383-388.
[14] G. Liu, L. Zhang, Factors and factorizations of graphs (in Chinese), Advances in Mathematics 29(2000), 289-296.
[15] L. Lovasz, Subgraphs with prescribed valencies, Journal of Combinatorial Theory 8(1970), 391-416.