SPECTRAL RADIUS AND HAMILTONICITY OF A GRAPH
Abstract
In this article, the lower graph order boundary obtained by V. Nikiforov, for which the generalization of the sufficient spectral criterion of Hamiltonicity of a graph is valid, has been reduced twice.
About the Author
V. I. BENEDIKTOVICH
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Belarus
References
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.
Review
Views: 823
Email this article 