СПЕКТРАЛЬНЫЙ РАДИУС И ГАМИЛЬТОНОВОСТЬ ГРАФА
Аннотация
В данной работе в два раза уменьшена нижняя граница порядка графов, полученная В. Никифоровым, для которых выполняется обобщение достаточного спектрального признака гамильтоновости графа, предложенного ранее.
Список литературы
1. Ore, O. Arc coverings of graphs / O. Ore // Ann. Mat. Pura Appl. – 1961. – Vol. 55. – P. 315–321.
2. Ore, O. Hamilton-connected graphs / O. Ore // J. Math. Pures Appl. – 1963. – Vol. 42. – P. 21– 27.
3. Bondy, A. A method in graph theory / A. Bondy, V. Chvátal // Discrete Math. – 1976. – Vol. 15. – P. 111–135.
4. Brualdi, R. A. On the spectral radius of complementary acyclic matrices of zeros and ones / R. A. Brualdi, E. S. Solheid // SIAM J. Algebraic Discrete Methods. – 1986. – Vol. 7, N 2. – P. 265–272.
5. Бенедиктович, В. И. Достаточное спектральное условие гамильтоновости графа / В. И. Бенедиктович // Докл. НАН Беларуси. – 2015. – Т. 59, № 5. – С. 5–12.
6. Nikiforov, V. Spectral radius and Hamiltonicity of graphs with large minimum degree / V. Nikiforov // arXiv:1602.01033 [math.CO] – http://arxiv.org/abs/1602.01033. – 2016.
7. Kelmans, A. K. On graphs with randomly deleted edges / A. K. Kelmans // Acta Math. Acad. Sci. Hung. – 1981. – Vol. 37. – P. 77–88.
8. Csikvari, P. On a conjecture of V. Nikiforov / P. Csikvari // Discrete Math. – 2009. – Vol. 309, N 13. – P. 4522–4526.
9. Brouwer, A. E. Spectra of graphs / A. E. Brouwer, W. H. Haemers. – Springer-Verlag, 2011.
10. Godsil, C. D. Algebraic graph theory / C. D. Godsil, G. F. Royle. – Springer-Verlag, 2001.
11. Прасолов, В. В. Многочлены / В. В. Прасолов. – М.: МЦНМО, 2001.
12. Chvátal, V. On Hamiltons ideals / V. Chvátal // J. Combin. Theory Ser. B. – 1972. – Vol. 12. – P. 163–168.
13. Hong, Y. A sharp upper bound of the spectral radius of graphs / Y. Hong, J. Shu, K. Fang // J. Combin. Theory. – 2001. – Vol. 81. – P. 177–183.
Рецензия
Просмотров: 786
Послать статью по эл. почте 