Difference betwwen the maximum degree and the index of a graph
https://doi.org/10.29235/1561-2430-2018-54-4-434-440
Abstract
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.
About the Author
V. I. Benediktovich
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Ph. D. (Physics and Mathematics), Leading Researcher
Belarus
Ph. D. (Physics and Mathematics), Leading Researcher
References
1. Godsil C., Royle G. Algebraic Graph Theory. New York, Springer, 2001. 463 p. https://doi.org/10.1007/9781461301639
2. Cioabă S. M. The spectral radius and the maximum degree of irregular graphs. The Electronic Journal of Combinatorics, 2007, vol. 14, pp. 1–10.
3. 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.
4. Liu 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.1249
5. Hayes 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.6
6. Chrobak 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
7.
Review
Views: 712
Email this article 