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...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Lugansk National Taras Shevchenko University
2018
|
| Schlagworte: | |
| Online Zugang: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/303 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Algebra and Discrete Mathematics |
Institution
Algebra and Discrete Mathematics| Zusammenfassung: | 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. |
|---|