О разности между максимальной степенью и индексом графа
https://doi.org/10.29235/1561-2430-2018-54-4-434-440
Аннотация
Рассматривается алгебраический параметр графа – разность между его максимальной степенью и спектральным радиусом. Хорошо известно, что этот графовый параметр является всегда неотрицательным и представляет собой некоторую меру отклонения графа от регулярности. В последние два десятилетия множество статей было посвящено изучению этого параметра. В частности, в 2007 г. американским математиком S. M. Cioabă получена его нижняя оценка, зависящая от порядка и диаметра графа. В 2017 г. при изучении верхней и нижней оценок для этого параметра M. R. Oboudi выдвинул гипотезу о том, что нижней оценкой данного параметра для произвольного графа является разность между максимальной степенью и спектральным радиусом цепи. Это очень похоже на аналогичное утверждение для спектрального радиуса произвольного графа, нижней границей которого тоже является спектральный радиус цепи. Здесь вышеуказанная гипотеза подтверждается для некоторых классов графов.
Об авторе
В. И. Бенедиктович
Институт математики Национальной академии наук Беларуси, Минск
Беларусь
кандидат физико-математических наук, ведущий научный сотрудник
Беларусь
кандидат физико-математических наук, ведущий научный сотрудник
Список литературы
1. Godsil, C. Algebraic Graph Theory / C. Godsil, G. Royle. – New York: Springer, 2001. – 463 p. https://doi.org/10.1007/ 978146130163¬9
2. Cioabă, S. M. The spectral radius and the maximum degree of irregular graphs / S. M. Cioabă // Electron. J. Combin. – 2007. – Vol. 14. – P. 1–10.
3. Oboudi, M. R. On the difference between the spectral radius and the maximum degree of graphs / M. R. Oboudi // Algebra and Discrete Math. – 2017. – Vol. 24. – P. 302–307.
4. Liu, B. A note on the largest eigenvalue of nonregular graphs / B. Liu, G. Li // Electron. J. Linear Algebra. – 2008. – Vol. 17, № 1. – P. 54–61. https://doi.org/10.13001/10813810.1249
5. Hayes, T. A simple condition implying rapid mixing of singlesite dynamics on spin systems / T. Hayes // Proc. 47th Annual IEEE Symposium on Foundation of Computer Science FOCS, 2006. – P. 39–46. https://doi.org/10.1109/focs.2006.6
6. Chrobak, M. Planar orientations with low outdegree and compaction of adjacency matrices / M. Chrobak, D. Eppstein // Theor. Comput. Sci. – 1991. – Vol. 86, № 2. – P. 243–266. https://doi.org/10.1016/03043975(91)900203
Рецензия
Просмотров: 710
Послать статью по эл. почте 