Панцикличность 1-жестких графов
https://doi.org/10.29235/1561-2430-2026-62-2-109-116
Аннотация
Более 50 лет назад В. Хватал ввел новый инвариант для графа, который измеряет, насколько крепко связаны друг с другом различные части графа, и назвал его жесткостью графа. С тех пор было получено множество результатов, в основном касающихся взаимосвязи между условиями жесткости и существованием в нем циклических структур, в частности, выяснению гамильтоновости и панцикличности графа. Многие важные результаты были получены с использованием спектральной теории графов. В 1976 г. Дж. Бонди выдвинул метагипотезу, согласно которой почти любое нетривиальное условие на графе, из которого следует, что граф гамильтонов, также влечет, что граф является панциклическим. Мы подтверждаем метагипотезу Бонди для 1-жестких графов в терминах спектрального радиуса.
Ключевые слова
При поддержке: Работа выполнена в рамках Государственной программы фундаментальных исследований «Междисциплинарные и синергетические исследования» («Конвергенция-2030»), задание «Модели, алгоритмы и вычислительная сложность задач дискретной математики», НИР «Модели, алгоритмы и вычислительная сложность комбинаторных и оптимизационных задач» при финансовой поддержке Национальной академии наук Беларуси.
Об авторе
В. И. Бенедиктович
Институт математики Национальной академии наук Беларуси
Беларусь
Беларусь
Бенедиктович Владимир Иванович – кандидат физико-математических наук, ведущий научный сотрудник
ул. Сурганова, 11, 220072, Минск
Список литературы
1. Chvá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-6
2. Bauer, 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-9
3. Toughness 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.3190090106
4. Bauer, 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-s
5. Бенедиктович, В. И. Сложность распознавания жесткости в классе (2t + 1)-регулярных графов // Весці Нацыянальнай акадэміі навук Беларусі. Серыя фізіка-матэматычных навук. – 2025. – Т. 61, № 4. – С. 299–305. https://doi.org/10.29235/1561-2430-2025-61-4-299-306.
6. Bondy, 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).
7. 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-4
8. Oberly, 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.3190030405
9. Clark, L. Hamiltonian properties of connected locally connected graphs / L. Clark // Congressus Numerantium. – 1981. – Vol. 32. – P. 199–204.
10. 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.004
11. Fana, 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.103701
12. Zhou, 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.1182463
13. Hong, 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.1997
14. Nikiforov, 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/S0963548301004928
15. Ainouche, 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-3
16. Hoà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-O
17. Brouwer, 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-6
Рецензия
Просмотров:
33
JATS XML
Послать статью по эл. почте 
