Pancyclicity of 1-tough graphs
https://doi.org/10.29235/1561-2430-2026-62-2-109-116
Abstract
More than 50 years ago, Chvátal introduced a new graph invariant that measures how tightly different parts of the graph are connected to each other, which he called graph toughness. From then on a lot of research has been obtained, mainly related to the relationship between toughness conditions and the existence of cyclic structures, in particular, determining whether the graph is Hamiltonian and pancyclic. Many important results have been obtained using spectral graph theory. Bondy in 1976, has suggested the metaconjecture that almost any nontrivial condition on a graph which implies that the graph is Hamiltonian also implies that the graph is pancyclic. We confirm the Bondy’s metaconjecture for 1-tough graphs in terms of spectral radius.
Supporting agencies: This work is carried out in the fra mework of the State Program for Fundamental Research «Interdisciplinary and synergistic research» (“Con vergence-2030”), assignment “Models, Algorithms, and Computational Complexity of Discrete Mathematics Problems”, research work “Models, Algorithms, and Computational Complexity of Combinatorial and Optimization Problems” with the financial support of the National Academy of Sciences of Belarus.
About the Author
V. I. Benediktovich
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Belarus
Vladimir I. Benediktovich – Ph. D. (Physics and Mathematics), Leading Researcher
11, Surganov Str., 220072, Minsk
References
1. Chvátal V. Tough graphs and Hamiltonian circuits. Discrete Mathematics, 1973, vol. 5, no. 3, pp. 215–228. https://doi.org/10.1016/0012-365X(73)90138-6
2. Bauer D., Broersma H. J., Veldman H. J. Not every 2-tough graph is Hamiltonian. Discrete Applied Mathematics, 2000, vol. 99, no. 1–3, pp. 317–321. https://doi.org/10.1016/S0166-218X(99)00141-9
3. Enomoto H., Jackson B., Katerinis P., Saito A. Toughness and the existence of k-factors. Journal of Graph Theory, 1985, vol. 9, no. 1, pp. 87–95. https://doi.org/10.1002/jgt.3190090106
4. Bauer D., Hakimi S. L., Schmeichel E. Recognizing tough graphs is NP-hard. Discrete Applied Mathematics, 1990, vol. 28, no. 3, pp. 191–195. https://doi.org/10.1016/0166-218x(90)90001-s
5. Benediktovich V. I. The complexity of the decision problem of toughness in the class of (2t + 1)-regular graphs. Vestsі Natsyyanalʼnai akademіі navuk Belarusі. Seryya fіzіka-matematychnykh navuk = Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics series, 2025, vol. 61, no. 4, pp. 299–306 (in Russian). https://doi.org/10.29235/1561-2430-2025-61-4-299-306
6. Bondy J. A. Pancyclic graphs: Recent results, infinite and finite sets. Infinite and Finite Sets. Colloquia mathematica Societatis János Bolyai; vol. 10. North-Holland Pub. Co., 1975, pp. 181–187.
7. Schmeichel E., Hakimi S. L. Pancyclic graphs and a conjecture of Bondy and Chvátal. Journal of Combinatorial Theory. Series B, 1974, vol. 17, no. 1, pp. 22–34. https://doi.org/10.1016/0095-8956(74)90043-4
8. Oberly D. J., Sumner D. P. Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian. Journal of Graph Theory, 1979, vol. 3, no. 4, pp. 351–356. https://doi.org/10.1002/jgt.3190030405
9. Clark L. Hamiltonian properties of connected locally connected graphs. Congressus Numerantium, 1981, vol. 32, pp. 199–204.
10. Benediktovich V. I. Spectral conditions of pancyclicity for t-tough graphs. Discrete Applied Mathematics, 2025, vol. 365, pp. 130–137. – https://doi.org/10.1016/j.dam.2025.01.004
11. Fana D., Lina H., Lu H. Toughness, hamiltonicity and spectral radius in graphs. European Journal of Combinatorics, 2023, vol. 110, art. ID 103701. https://doi.org/10.1016/j.ejc.2023.103701
12. Zhou Q., Wang L. Some sufficient spectral conditions on Hamilton-connected and traceable graphs. Linear Multilinear Algebra, 2017, vol. 65, no. 2, pp. 224–234. https://doi.org/10.1080/03081087.2016.1182463
13. Hong Y., Shu J., Fang K. A sharp upper bound of the spectral radius of graphs. Journal of Combinatorial Theory. Series B, 2001, vol. 81, no. 2, pp. 177–183. https://doi.org/10.1006/jctb.2000.1997
14. Nikiforov V. Some inequalities for the largest eigenvalue of a graph. Combinatorics, Probability and Computing, 2002, vol. 11, no. 2, pp. 179–189. https://doi.org/10.1017/S0963548301004928
15. Ainouche A. Dirac’s type sufficient conditions for Hamiltonicity and pancyclicity. Graphs and Combinatorics, 2009, vol. 25, no. 2, pp. P. 129–137. https://doi.org/10.1007/s00373-008-0835-3
16. Hoàng C. Hamiltonian degree conditions for tough graphs. Discrete Mathematics, 1995, vol. 142, no. 1–3, pp. 121– 139. https://doi.org/10.1016/0012-365X(93)E0214-O
17. Brouwer A. E., Haemers W. H. Spectra of Graphs. New York, Springer, 2011. 250 p. https://doi.org/10.1007/978-1-4614-1939-6
Review
Views:
36
JATS XML
Email this article 
