On the difference between the spectral radius and the maximum degree of graphs
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 regu...
Збережено в:
| Опубліковано в: : | Algebra and Discrete Mathematics |
|---|---|
| Дата: | 2017 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2017
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/156636 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | 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 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862533029247844352 |
|---|---|
| author | Oboudi, M.R. |
| author_facet | Oboudi, M.R. |
| citation_txt | 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 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| 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.
|
| first_indexed | 2025-11-24T06:35:37Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-156636 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-11-24T06:35:37Z |
| publishDate | 2017 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Oboudi, M.R. 2019-06-18T18:15:53Z 2019-06-18T18:15:53Z 2017 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. https://nasplib.isofts.kiev.ua/handle/123456789/156636 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. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics On the difference between the spectral radius and the maximum degree of graphs Article published earlier |
| spellingShingle | On the difference between the spectral radius and the maximum degree of graphs Oboudi, M.R. |
| title | On the difference between the spectral radius and the maximum degree of graphs |
| title_full | On the difference between the spectral radius and the maximum degree of graphs |
| title_fullStr | On the difference between the spectral radius and the maximum degree of graphs |
| title_full_unstemmed | On the difference between the spectral radius and the maximum degree of graphs |
| title_short | On the difference between the spectral radius and the maximum degree of graphs |
| title_sort | on the difference between the spectral radius and the maximum degree of graphs |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/156636 |
| work_keys_str_mv | AT oboudimr onthedifferencebetweenthespectralradiusandthemaximumdegreeofgraphs |