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| Summary: | 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. |
|---|