vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2026-62-2-109-116vestifm-900Research ArticleМАТЕМАТИКАMATHEMATICSПанцикличность 1-жестких графовPancyclicity of 1-tough graphsБенедиктовичВ. И.BenediktovichV. I.

Бенедиктович Владимир Иванович – кандидат физико-математических наук, ведущий научный сотрудник

ул. Сурганова, 11, 220072, Минск

Vladimir I. Benediktovich – Ph. D. (Physics and Mathematics), Leading Researcher

11, Surganov Str., 220072, Minsk

vbened@im.bas-net.byИнститут математики Национальной академии наук БеларусиБеларусьInstitute of Mathematics of the National Academy of Sciences of BelarusBelarus202610072026622109116Copyright © Бенедиктович В.И., 20262026Бенедиктович В.И.Benediktovich V.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/900

Более 50 лет назад В. Хватал ввел новый инвариант для графа, который измеряет, насколько крепко связаны друг с другом различные части графа, и назвал его жесткостью графа. С тех пор было получено множество результатов, в основном касающихся взаимосвязи между условиями жесткости и существованием в нем циклических структур, в частности, выяснению гамильтоновости и панцикличности графа. Многие важные результаты были получены с использованием спектральной теории графов. В 1976 г. Дж. Бонди выдвинул метагипотезу, согласно которой почти любое нетривиальное условие на графе, из которого следует, что граф гамильтонов, также влечет, что граф является панциклическим. Мы подтверждаем метагипотезу Бонди для 1-жестких графов в терминах спектрального радиуса.

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.

гамильтоновостьпанцикличностьматрица смежностиспектральный радиус графаt-жесткий графHamiltonicitypancyclicityadjacency matrixspectral radius of a grapht-tough graphРабота выполнена в рамках Государственной программы фундаментальных исследований «Междисциплинарные и синергетические исследования» («Конвергенция-2030»), задание «Модели, алгоритмы и вычислительная сложность задач дискретной математики», НИР «Модели, алгоритмы и вычислительная сложность комбинаторных и оптимизационных задач» при финансовой поддержке Национальной академии наук Беларуси.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.ReferencesChvátal, V. Tough graphs and Hamiltonian circuits / V. Chvátal // Discrete Mathematics. – 1973. – Vol. 5, № 3. – P. 215–228. https://doi.org/10.1016/0012-365X(73)90138-6Chvá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-6Bauer, D. Not every 2-tough graph is Hamiltonian / D. Bauer, H. J. Broersma, H. J. Veldman // Discrete Applied Mathematics. – 2000. – Vol. 99, № 1–3. – P. 317–321. https://doi.org/10.1016/S0166-218X(99)00141-9Bauer 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-9Toughness and the existence of k-factors / H. Enomoto, B. Jackson, P. Katerinis, A. Saito // Journal of Graph Theory. – 1985. – Vol. 9, № 1. – P. 87–95. https://doi.org/10.1002/jgt.3190090106Enomoto 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.3190090106Bauer, D. Recognizing tough graphs is NP-hard / D. Bauer, S. L. Hakimi, E. Schmeichel // Discrete Applied Mathematics. – 1990. – Vol. 28, № 3. – P. 191–195. https://doi.org/10.1016/0166-218x(90)90001-sBauer 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Бенедиктович, В. И. Сложность распознавания жесткости в классе (2t + 1)-регулярных графов // Весці Нацыянальнай акадэміі навук Беларусі. Серыя фізіка-матэматычных навук. – 2025. – Т. 61, № 4. – С. 299–305. https://doi.org/10.29235/1561-2430-2025-61-4-299-306.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-306Bondy, J. A. Pancyclic graphs: Recent results, infinite and finite sets / J. A. Bondy // Infinite and Finite Sets. – NorthHolland Pub. Co., 1975. – P. 181–187. – (Colloquia mathematica Societatis János Bolyai; vol. 10).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.Schmeichel, E. Pancyclic graphs and a conjecture of Bondy and Chvátal / E. Schmeichel, S. L. Hakimi // Journal of Combinatorial Theory. Series B. – 1974. – Vol. 17, № 1. – P. 22–34. https://doi.org/10.1016/0095-8956(74)90043-4Schmeichel 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-4Oberly, D. J. Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian / D. J. Oberly, D. P. Sumner // Journal of Graph Theory. – 1979. – Vol. 3, № 4. – P. 351–356. https://doi.org/10.1002/jgt.3190030405Oberly 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.3190030405Clark, L. Hamiltonian properties of connected locally connected graphs / L. Clark // Congressus Numerantium. – 1981. – Vol. 32. – P. 199–204.Clark L. Hamiltonian properties of connected locally connected graphs. Congressus Numerantium, 1981, vol. 32, pp. 199–204.Benediktovich, V. I. Spectral conditions of pancyclicity for t-tough graphs / V. I. Benediktovich // Discrete Applied Mathematics. – 2025. – Vol. 365. – P. 130–137. – https://doi.org/10.1016/j.dam.2025.01.004Benediktovich 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.004Fana, D. Toughness, hamiltonicity and spectral radius in graphs / D. Fana, H. Lina, H. Lu // European Journal of Combinatorics. – 2023. – Vol. 110. – Art. ID 103701. https://doi.org/10.1016/j.ejc.2023.103701Fana 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.103701Zhou, Q. Some sufficient spectral conditions on Hamilton-connected and traceable graphs / Q. Zhou, L. Wang // Linear Multilinear Algebra. – 2017. – Vol. 65, № 2. – P. 224–234. https://doi.org/10.1080/03081087.2016.1182463Zhou 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.1182463Hong, Y. A sharp upper bound of the spectral radius of graphs / Y. Hong, J. Shu, K. Fang // Journal of Combinatorial Theory. Series B. – 2001. – Vol. 81, № 2. – P. 177–183. https://doi.org/10.1006/jctb.2000.1997Hong 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.1997Nikiforov, V. Some inequalities for the largest eigenvalue of a graph / V. Nikiforov // Combinatorics, Probability and Computing. – 2002. – Vol. 11, № 2. – P. 179–189. https://doi.org/10.1017/S0963548301004928Nikiforov 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/S0963548301004928Ainouche, A. Dirac’s type sufficient conditions for Hamiltonicity and pancyclicity / A. Ainouche // Graphs and Combinatorics. – 2009. – Vol. 25, № 2. – P. 129–137. https://doi.org/10.1007/s00373-008-0835-3Ainouche 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-3Hoàng, C. Hamiltonian degree conditions for tough graphs / C. Hoàng // Discrete Mathematics. – 1995. – Vol. 142, № 1–3. – P. 121–139. https://doi.org/10.1016/0012-365X(93)E0214-OHoà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-OBrouwer, A. E. Spectra of Graphs / A. E. Brouwer, W. H. Haemers. – New York: Springer, 2011. – 250 p. https://doi.org/10.1007/978-1-4614-1939-6Brouwer A. E., Haemers W. H. Spectra of Graphs. New York, Springer, 2011. 250 p. https://doi.org/10.1007/978-1-4614-1939-6

The authors declare that there are no conflicts of interest present.