Abstract
Let a, b, k be nonnegative integers with 2 ≤ a < 6. A graph G is called a k-Hamiltonian graph if G − U contains a Hamiltonian cycle for any subset U ⊆ V(G) with ∣U∣ = k. An [a, b]-factor F of G is called a Hamiltonian [a, b]-factor if F contains a Hamiltonian cycle. If G − U admits a Hamiltonian [a, b]-factor for any subset U ⊆ V(G) with ∣U∣ = k, then we say that G has a k-Hamiltonian [a, b]-factor. Suppose that G is a k-Hamiltonian graph of order n with \(n\geq\frac{(a+b-4)(2a+b+k-6)}{b-2}+k\) and δ(G) ≥ a + k. In this paper, it is proved that G admits a k-Hamiltonian [a, b]-factor if \(\max\{d_{G}(x),d_{G}(y)\}\geq\frac{(a-2)n+(b-2)k}{a+b-4}+2\) for each pair of nonadjacent vertices x and y in G.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bekkai, S. Minimum degree, independence number and pseudo [2, b]-factors in graphs. Discrete Applied Mathematics, 162: 108–114 (2014)
Cai, M., Li, Y., Kano, M. A [k, k + 1]-factor containing given Hamiltonian cycle. Science in China, Ser. A, 41: 933–938 (1998)
Furuya, M., Maezawa, S., Matsubara, R., Matsuda, H., Tsuchiya, S., Yashima, T. Degree sum condition for the existence of spanning k-trees in star-free graphs. Discussiones Mathematicae Graph Theory, DOI: https://doi.org/10.7151/dmgt.2234
Gao, W., Wang, W., Chen, Y. Tight bounds for the existence of path factors in network vulnerability parameter settings. International Journal of Intelligent Systems, 36: 1133–1158 (2021)
Gao, W., Wang, W., Guirao, J. The extension degree conditions for fractional factor. Acta Mathematica Sinica-English Series, 36: 305–317 (2020)
Haghparast, N., Kiani, D. Edge-connectivity and edges of even factors of graphs. Discussiones Mathematicae Graph Theory, 39: 357–364 (2019)
Lovász, L. Subgraphs with prescribed valencies. Journal of Combinatorial Theory, 8: 391–416 (1970)
Lv, X. A degree condition for fractional (g, f, n)-critical covered graphs. AIMS Mathematics, 5: 872–878 (2020)
Matsuda, H. Degree conditions for Hamiltonian graphs to have [a, b]-factors containing a given Hamiltonian cycle. Discrete Mathematics, 280: 241–250 (2004)
Matsuda, H. Degree conditions for the existence of [k, k + 1]-factors containing a given Hamiltonian cycle. Australian Journal of Combinatorics, 26: 273–281 (2002)
Ore, O. Note on Hamiltonian circuits. The American Mathematical Monthly, 67: 55 (1960)
Tsuchiya, S., Yashima, T. A degree condition implying Ore-type condition for even [2, b]-factors in graphs. Discussiones Mathematicae Graph Theory, 37: 797–809 (2017)
Wang, S., Zhang, W. Research on fractional critical covered graphs. Problems of Information Transmission, 56: 270–277 (2020)
Yuan, Y., Hao, R. A neighborhood union condition for fractional ID-[a, b]-factor-critical graphs. Acta Mathematicae Applicatae Sinica-English Series, 34: 775–781 (2018)
Yuan, Y., Hao, R. Independence number, connectivity and all fractional (a, b, k)-critical graphs. Discussiones Mathematicae Graph Theory, 39: 183–190 (2019)
Zhou, S. Binding numbers and restricted fractional (g, f)-factors in graphs. Discrete Applied Mathematics, DOI: https://doi.org/10.1016/j.dam.2020.10.017
Zhou, S. Remarks on path factors in graphs. RAIRO-Operations Research, 54: 1827–1834 (2020)
Zhou, S. Some results on path-factor critical avoidable graphs. Discussiones Mathematicae Graph Theory, DOI: https://doi.org/10.7151/dmgt.2364
Zhou, S., Bian, Q., Sun, Z. Two sufficient conditions for component factors in graphs. Discussiones Mathematicae Graph Theory, DOI: https://doi.org/10.7151/dmgt.2401
Zhou, S., Sun, Z. Binding number conditions for P≥2-factor and P≥3-factor uniform graphs. Discrete Mathematics, 343: 111715 (2020)
Zhou, S., Sun, Z. Some existence theorems on path factors with given properties in graphs. Acta Mathematica Sinica-English Series, 36: 917–928 (2020)
Zhou, S., Sun, Z., Pan, Q. A sufficient condition for the existence of restricted fractional (g, f)-factors in graphs. Problems of Information Transmission, 56: 332–344 (2020)
Zhou, S., Xu, Y., Sun, Z. Degree conditions for fractional (a, b, k)-critical covered graphs. Information Processing Letters, 152: 105838 (2019)
Zhou, S., Yang, F., Xu, L. Two sufficient conditions for the existence of path factors in graphs. Scientia Iranica, 26: 3510–3514 (2019)
Zhou, S., Zhang, T., Xu, Z. Subgraphs with orthogonal factorizations in graphs. Discrete Applied Mathematics, 286: 29–34 (2020)
Acknowledgments
The authors would like to thank the referees for their valuable comments and helpful suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is supported by the National Natural Science Foundation of China (Grant No. 11371009) and the National Social Science Foundation of China (Grant No. 14AGL001), and sponsored by Six Big Talent Peak of Jiangsu Province (Grant No. JY-022) and 333 Project of Jiangsu Province.
Rights and permissions
About this article
Cite this article
Wu, J., Zhou, Sz. Degree Conditions for k-Hamiltonian [a, b]-factors. Acta Math. Appl. Sin. Engl. Ser. 37, 232–239 (2021). https://doi.org/10.1007/s10255-021-1005-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-021-1005-0