On the difference between the spectral radius and the maximum degree of graphs
Let \(G\) be a graph with the eigenvalues \(\lambda_1(G)\geq\cdots\geq\lambda_n(G)\). The largest eigenvalue of \(G\), \(\lambda_1(G)\), is called the spectral radius of \(G\). Let \(\beta(G)=\Delta(G)-\lambda_1(G)\), where \(\Delta(G)\) is the maximum degree of vertices of \(G\). It is known that i...
Saved in:
| Date: | 2018 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Lugansk National Taras Shevchenko University
2018
|
| Subjects: | |
| Online Access: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/303 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Algebra and Discrete Mathematics |
Institution
Algebra and Discrete Mathematics| id |
admjournalluguniveduua-article-303 |
|---|---|
| record_format |
ojs |
| spelling |
admjournalluguniveduua-article-3032018-04-26T02:43:18Z On the difference between the spectral radius and the maximum degree of graphs Oboudi, Mohammad Reza tree, eigenvalues of graphs, spectral radius of graphs, maximum degree 05C31, 05C50, 15A18 Let \(G\) be a graph with the eigenvalues \(\lambda_1(G)\geq\cdots\geq\lambda_n(G)\). The largest eigenvalue of \(G\), \(\lambda_1(G)\), is called the spectral radius of \(G\). Let \(\beta(G)=\Delta(G)-\lambda_1(G)\), where \(\Delta(G)\) is the maximum degree of vertices of \(G\). It is known that if \(G\) is a connected graph, then \(\beta(G)\geq0\) and the equality holds if and only if \(G\) is regular. In this paper we study the maximum value and the minimum value of \(\beta(G)\) among all non-regular connected graphs. In particular we show that for every tree \(T\) with \(n\geq3\) vertices, \(n-1-\sqrt{n-1}\geq\beta(T)\geq 4\sin^2(\frac{\pi}{2n+2})\). Moreover, we prove that in the right side the equality holds if and only if \(T\cong P_n\) and in the other side the equality holds if and only if \(T\cong S_n\), where \(P_n\) and \(S_n\) are the path and the star on \(n\) vertices, respectively. Lugansk National Taras Shevchenko University 2018-01-24 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/303 Algebra and Discrete Mathematics; Vol 24, No 2 (2017) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/303/pdf_1 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/303/281 Copyright (c) 2018 Algebra and Discrete Mathematics |
| institution |
Algebra and Discrete Mathematics |
| baseUrl_str |
|
| datestamp_date |
2018-04-26T02:43:18Z |
| collection |
OJS |
| language |
English |
| topic |
tree eigenvalues of graphs spectral radius of graphs maximum degree 05C31 05C50 15A18 |
| spellingShingle |
tree eigenvalues of graphs spectral radius of graphs maximum degree 05C31 05C50 15A18 Oboudi, Mohammad Reza On the difference between the spectral radius and the maximum degree of graphs |
| topic_facet |
tree eigenvalues of graphs spectral radius of graphs maximum degree 05C31 05C50 15A18 |
| format |
Article |
| author |
Oboudi, Mohammad Reza |
| author_facet |
Oboudi, Mohammad Reza |
| author_sort |
Oboudi, Mohammad Reza |
| title |
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_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_sort |
on the difference between the spectral radius and the maximum degree of graphs |
| description |
Let \(G\) be a graph with the eigenvalues \(\lambda_1(G)\geq\cdots\geq\lambda_n(G)\). The largest eigenvalue of \(G\), \(\lambda_1(G)\), is called the spectral radius of \(G\). Let \(\beta(G)=\Delta(G)-\lambda_1(G)\), where \(\Delta(G)\) is the maximum degree of vertices of \(G\). It is known that if \(G\) is a connected graph, then \(\beta(G)\geq0\) and the equality holds if and only if \(G\) is regular. In this paper we study the maximum value and the minimum value of \(\beta(G)\) among all non-regular connected graphs. In particular we show that for every tree \(T\) with \(n\geq3\) vertices, \(n-1-\sqrt{n-1}\geq\beta(T)\geq 4\sin^2(\frac{\pi}{2n+2})\). Moreover, we prove that in the right side the equality holds if and only if \(T\cong P_n\) and in the other side the equality holds if and only if \(T\cong S_n\), where \(P_n\) and \(S_n\) are the path and the star on \(n\) vertices, respectively. |
| publisher |
Lugansk National Taras Shevchenko University |
| publishDate |
2018 |
| url |
https://admjournal.luguniv.edu.ua/index.php/adm/article/view/303 |
| work_keys_str_mv |
AT oboudimohammadreza onthedifferencebetweenthespectralradiusandthemaximumdegreeofgraphs |
| first_indexed |
2025-12-02T15:26:40Z |
| last_indexed |
2025-12-02T15:26:40Z |
| _version_ |
1850411868347170816 |