On the difference between the spectral radius and the maximum degree of graphs
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
On the difference between the spectral radius and the maximum degree of graphs
|
|
| Creator |
Oboudi, M.R.
|
|
| Description |
Let G be a graph with the eigenvalues λ₁(G)≥⋯≥λn(G). The largest eigenvalue of G, λ₁(G), is called the spectral radius of G. Let β(G)=Δ(G)−λ₁(G), where Δ(G) is the maximum degree of vertices of G. It is known that if G is a connected graph, then β(G)≥0 and the equality holds if and only if G is regular. In this paper we study the maximum value and the minimum value of β(G) among all non-regular connected graphs. In particular we show that for every tree T with n≥3 vertices, n−1−√(n−1) ≥ β(T) ≥ 4sin²(π/(2n+2)). Moreover, we prove that in the right side the equality holds if and only if T≅Pn and in the other side the equality holds if and only if T≅Sn, where Pn and Sn are the path and the star on n vertices, respectively.
|
|
| Date |
2019-06-18T18:15:53Z
2019-06-18T18:15:53Z 2017 |
|
| Type |
Article
|
|
| Identifier |
On the difference between the spectral radius and the maximum degree of graphs / M.R. Oboudi // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 2. — С. 302-307. — Бібліогр.: 17 назв. — англ.
1726-3255 2010 MSC:05C31, 05C50, 15A18. http://dspace.nbuv.gov.ua/handle/123456789/156636 |
|
| Language |
en
|
|
| Relation |
Algebra and Discrete Mathematics
|
|
| Publisher |
Інститут прикладної математики і механіки НАН України
|
|