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-2018-54-4-434-440vestifm-350Research ArticleМАТЕМАТИКАMATHEMATICSО разности между максимальной степенью и индексом графаDifference betwwen the maximum degree and the index of a graphБенедиктовичВ. И.BenediktovichV. I.

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

Ph. D. (Physics and Mathematics), Leading Researcher

vbened@im.bas-net.byИнститут математики Национальной академии наук Беларуси, МинскInstitute of Mathematics of the National Academy of Sciences of Belarus201809012019544434440Copyright © Бенедиктович В.И., 20192019Бенедиктович В.И.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/350

Рассматривается алгебраический параметр графа – разность между его максимальной степенью и спектральным радиусом. Хорошо известно, что этот графовый параметр является всегда неотрицательным и представляет собой некоторую меру отклонения графа от регулярности. В последние два десятилетия множество статей было посвящено изучению этого параметра. В частности, в 2007 г. американским математиком S. M. Cioabă получена его нижняя оценка, зависящая от порядка и диаметра графа. В 2017 г. при изучении верхней и нижней оценок для этого параметра M. R. Oboudi выдвинул гипотезу о том, что нижней оценкой данного параметра для произвольного графа является разность между максимальной степенью и спектральным радиусом цепи. Это очень похоже на аналогичное утверждение для спектрального радиуса произвольного графа, нижней границей которого тоже является спектральный радиус цепи. Здесь вышеуказанная гипотеза подтверждается для некоторых классов графов.

An algebraic parameter of a graph – a difference between its maximum degree and its spectral radius is considered in this paper. It is well known that this graph parameter is always nonnegative and represents some measure of deviation of a graph from its regularity. In the last two decades, many papers have been devoted to the study of this parameter. In particular, its lower bound depending on the graph order and diameter was obtained in 2007 by mathematician S. M. Cioabă. In 2017 when studying the upper and the lower bounds of this parameter, M. R. Oboudi made a conjecture that the lower bound of a given parameter for an arbitrary graph is the difference between a maximum degree and a spectral radius of a chain. This is very similar to the analogous statement for the spectral radius of an arbitrary graph whose lower boundary is also the spectral radius of a chain. In this paper, the above conjecture is confirmed for some graph classes.

регулярныйпланарныйпоследовательно-параллельныйунициклическийрасщепляемый графмаксимальная степеньматрица смежностиспектральный радиусregularplanarseries-parallelunicyclicsplit graphmaximum degreeadjacency matrixspectral radiusReferencesGodsil, C. Algebraic Graph Theory / C. Godsil, G. Royle. – New York: Springer, 2001. – 463 p. https://doi.org/10.1007/ 978146130163¬9Godsil C., Royle G. Algebraic Graph Theory. New York, Springer, 2001. 463 p. https://doi.org/10.1007/9781461301639Cioabă, S. M. The spectral radius and the maximum degree of irregular graphs / S. M. Cioabă // Electron. J. Combin. – 2007. – Vol. 14. – P. 1–10.Cioabă S. M. The spectral radius and the maximum degree of irregular graphs. The Electronic Journal of Combinatorics, 2007, vol. 14, pp. 1–10.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.Oboudi M. R. On the difference between the spectral radius and the maximum degree of graphs. Algebra and Discrete Mathematics, 2017, vol. 24, рр. 302–307.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.1249Liu B., Li G. A note on the largest eigenvalue of nonregular graphs. Electronic Journal of Linear Algebra, 2008, vol. 17, no. 1, pp. 54–61. https://doi.org/10.13001/10813810.1249Hayes, 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.6Hayes T. A simple condition implying rapid mixing of singlesite dynamics on spin systems. Proc. 47th Annual IEEE Symposium on Foundation of Computer Science FOCS, 2006, pp. 39–46. https://doi.org/10.1109/focs.2006.6Chrobak, 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)900203Chrobak M., Eppstein D. Planar orientations with low outdegree and compaction of adjacency matrices. Theoretical Computer Science, 1991, vol. 86, no. 2, pp. 243–266. https://doi.org/10.1016/0304¬3975(91)900203

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