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

Mohammad Reza Oboudi

Algebra and discrete mathematics, Tome 24 (2017) no. 2, pp. 302-307

Résumé

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.

Détail

Keywords: tree, eigenvalues of graphs, spectral radius of graphs, maximum degree.

Bibliographie

[1] R. A. Brualdi, A. J. HoIman, “On the spectral radius of a $(0,1)$ matrix”, Linear Algebra and its Applications, 65 (1985), 133–146 | DOI | MR | Zbl

[2] D. Cao, Y. Hong, “The distribution of eigenvalues of graphs”, Linear Algebra and its Applications, 216 (1995), 211–224 | DOI | MR | Zbl

[3] S. M. Cioabă, “The spectral radius and the maximum degree of irregular graphs”, The Electronic Journal of Combinatorics, 14 (2007), R38 | MR | Zbl

[4] D.Cvetković, P. Rowlinson, S. Simić, An introduction to the theory of graph spectra, London Mathematical Society Student Texts, 75, Cambridge University Press, Cambridge, 2010 | MR | Zbl

[5] K. Ch. Das, P. Kumar, “Some new bounds on the spectral radius of graphs”, Discrete Mathematics, 281 (2004), 149–161 | DOI | MR | Zbl

[6] G. J. Ming, T.Sh.Wang, “On the spectral radius of trees”, Linear Algebra and its Applications, 329 (2001), 1–8 | DOI | MR | Zbl

[7] M. R. Oboudi, “Bipartite graphs with at most six non-zero eigenvalues”, Ars Mathematica Contemporanea, 11 (2016), 315–325 | MR | Zbl

[8] M. R. Oboudi, “Characterization of graphs with exactly two non-negative eigenvalues”, Ars Mathematica Contemporanea, 12 (2017), 271–286 | MR | Zbl

[9] M. R. Oboudi, “Cospectrality of complete bipartite graphs”, Linear and Multilinear Algebra, 64 (2016), 2491–2497 | DOI | MR | Zbl

[10] M. R. Oboudi, “Energy and Seidel energy of graphs”, MATCH Communications in Mathematical and in Computer Chemistry, 75 (2016), 291–303 | MR

[11] M. R. Oboudi, “On the eigenvalues and spectral radius of starlike trees”, Aequationes Mathematicae | DOI

[12] M. R. Oboudi, “On the third largest eigenvalue of graphs”, Linear Algebra and its Applications, 503 (2016), 164–179 | DOI | MR | Zbl

[13] L. Shi, “Bounds on the (Laplacian) spectral radius of graphs”, Linear Algebra and its Applications, 422 (2007), 755–770 | DOI | MR | Zbl

[14] D. Stevanović, “Bounding the largest eigenvalue of trees in terms of the largest vertex degree”, Linear Algebra and its Applications, 360 (2003), 35–42 | DOI | MR | Zbl

[15] D. Stevanović, I. Gutman, M. U. Rehman, “On spectral radius and energy of complete multipartite graphs”, Ars Mathematica Contemporanea, 9 (2015), 109–113 | MR | Zbl

[16] B. Wu, E. Xiao,Y. Hong, “The spectral radius of trees on $k$ pendant vertices”, Linear Algebra and its Applications, 395 (2005), 343–349 | DOI | MR | Zbl

[17] A. Yu, M.Lu, F. Tian, “On the spectral radius of graphs”, Linear Algebra and its Applications, 387 (2004), 41–49 | DOI | MR | Zbl