On the difference between the spectral radius and the maximum degree of graphs

Mohammad Reza Oboudi


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.


tree, eigenvalues of graphs, spectral radius of graphs, maximum degree

Full Text:



  • There are currently no refbacks.