Abstract
Let a, b and k be nonnegative integers with a ≥ 2 and b ≥ a(k + 1) + 2. A graph G is called a k-Hamiltonian graph if after deleting any k vertices of G the remaining graph of G has a Hamiltonian cycle. A graph G is said to have a k-Hamiltonian [a, b]-factor if after deleting any k vertices of G the remaining graph of G admits a Hamiltonian [a, b]-factor. Let G is a k-Hamiltonian graph of order n with n ≥ a + k + 2. In this paper, it is proved that G contains a k-Hamiltonian [a, b]-factor if δ(G) ≥ a + k and \(\delta \left(G \right) \ge I\left(G \right) \ge a - 1 + {{a\left({k + 1} \right)} \over {b - 2}}\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Cai, M., Fang, Q., Li, Y. Hamiltonian [k, k + 1]-factor. Advances in Mathematics (China), 32(6): 722–726 (2003)
Chang, R. A sufficient condition for (a, b, k)-critical graphs. Journal of Shandong University (Natural Science), 45(4): 21–23 (2010)
Gao, Y., Li, G., Li, X. Degree conditions for the existence of a k-factor containing a given Hamiltonian cycle. Discrete Mathematics, 309: 2373–2381 (2009)
Gao, W., Guirao, J., Chen, Y. A toughness condition for fractional (k, m)-deleted graphs revisited. Acta Mathematica Sinica, English Series, 35: 1227–1237 (2019)
Gao, W., Wang, W., Guirao, J. The extension degree conditions for fractional factor. Acta Mathematica Sinica, English Series, 36: 305–317 (2020)
Gu, X. Regular factors and eigenvalues of regular graphs. European Journal of Combinatorics, 42: 15–25 (2014)
Katerinis, P. Toughness of graphs and the existence of factors. Discrete Mathematics, 80: 81–92 (1990)
Kimura, K. f-factors, complete-factors, and component-deleted subgraphs. Discrete Mathematics, 313: 1452–1463 (2013)
Kouider, M., Ouatiki, S. Sufficient condition for the existence of an even [a, b]-factor in graph. Graphs and Combinatorics, 29: 1051–1057 (2013)
Lovász, L. Subgraphs with prescribed valencies. Journal of Combinatorial Theory, 8: 391–416 (1970)
Lu, H., Wang, D. On Cui-Kano’s characterization problem on graph factors. Journal of Graph Theory, 74: 335–343 (2013)
Lv, X. A degree condition for fractional (g, f, n)-critical covered graphs. AIMS Mathematics, 5(2): 872–878 (2020)
Ma, Y., Liu, G. Fractional factors and isolated toughness of graphs. Mathematica Applicata, 19(1): 188–194 (2006)
Ma, Y., Liu, G. Isolated toughness and existence of fractional factors in graphs. Acta Mathematicae Applicatae Sinica (Chinese Series), 26: 133–140 (2003)
Matsuda, H. Degree conditions for Hamiltonian graphs to have [a, b]-factors containing a given Hamiltonian cycle. Discrete Mathematics, 280: 241–250 (2004)
Wei, B., Zhu, Y. Hamiltonian k-factors in graphs. Journal of Graph Theory, 25: 217–227 (1997)
Zhou, S. Remarks on orthogonal factorizations of digraphs. International Journal of Computer Mathematics, 91(10): 2109–2117 (2014)
Zhou, S. Remarks on path factors in graphs. RAIRO-Operations Research, DOI: https://doi.org/10.1051/ro/2019111
Zhou, S. Some results about component factors in graphs. RAIRO-Operations Research, 53(3): 723–730 (2019)
Zhou, S. Toughness and the existence of Hamiltonian [a, b]-factors of graphs. Utilitas Mathematica, 90: 187–197 (2013)
Zhou, S., Sun, Z. Binding number conditions for P≥2-factor and P≥3-factor uniform graphs. Discrete Mathematics, 343(3): 111715 (2020) DOI: https://doi.org/10.1016/j.disc.2019.111715
Zhou, S., Sun, Z. Some existence theorems on path factors with given properties in graphs. Acta Mathematica Sinica, English Series, DOI: https://doi.org/10.1007/s10114-020-9224-5
Zhou, S., Liu, H., Xu, Y. Binding numbers for fractional (a, b, k)-critical covered graphs. Proceedings of the Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science, 21(2): 115–121 (2020)
Zhou, S., Xu, Y., Sun, Z. Degree conditions for fractional (a, b, k)-critical covered graphs. Information Processing Letters, 152: 105838 (2019) DOI: https://doi.org/10.1016/j.ipl.2019.105838
Zhou, S., Xu, L., Xu, Z. Remarks on fractional ID-k-factor-critical graphs. Acta Mathematicae Applicatae Sinica, English Series, 35(2): 458–464 (2019)
Zhou, S., Yang, F., Xu, L. Two sufficient conditions for the existence of path factors in graphs. Scientia Iranica, 26(6): 3510–3514 (2019)
Zhou, S., Zhang, T., Xu, Z. Subgraphs with orthogonal factorizations in graphs. Discrete Applied Mathematics, DOI: https://doi.org/10.1016/j.dam.2019.12.011
Acknowledgments
The authors are grateful to the anonymous referees for giving many helpful comments and suggestions in improving this paper.
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
Sun, Zr., Zhou, Sz. Isolated Toughness and k-Hamiltonian [a, b]-factors. Acta Math. Appl. Sin. Engl. Ser. 36, 539–544 (2020). https://doi.org/10.1007/s10255-020-0963-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-020-0963-y