Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
spectral radius; Laplacian eigenvalue; strongly regular graph
spectral radius; Laplacian eigenvalue; strongly regular graph
Summary:
Let $G$ be a graph with $n$ vertices, $m$ edges and a vertex degree sequence $(d_1, d_2, \dots , d_n)$, where $d_1 \ge d_2 \ge \dots \ge d_n$. The spectral radius and the largest Laplacian eigenvalue are denoted by $\rho (G)$ and $\mu (G)$, respectively. We determine the graphs with \[ \rho (G) = \frac{d_n - 1}{2} + \sqrt{2m - nd_n + \frac{(d_n +1)^2}{4}} \] and the graphs with $d_n\ge 1$ and \[ \mu (G) = d_n + \frac{1}{2} + \sqrt {\sum _{i=1}^n d_i (d_i-d_n) + \Bigl (d_n - \frac{1}{2} \Bigr )^2}. \] We also present some sharp lower bounds for the Laplacian eigenvalues of a connected graph.
References:
[1] R. A. Brualdi: From the Editor in Chief. Linear Algebra Appl. 360 (2003), 279–283. MR 1728495
[2] D. M. Cvetkovič, M. Doob and H. Sachs: Spectra of Graphs. DVW, Berlin, 1980. MR 0572262
[3] M. Fiedler: Algebraic conectivity of graphs. Czechoslovak Math. J. 23 (1973), 298–305. MR 0318007
[4] R. Grone and R. Merris: The Laplacian spectrum of a graph (II). SIAM J. Discrete Math. 7 (1994), 221–229. DOI 10.1137/S0895480191222653 | MR 1271994
[5] Y. Hong: Bounds of eigenvalues of graphs. Discrete Math. 123 (1993), 65–74. DOI 10.1016/0012-365X(93)90007-G | MR 1256082 | Zbl 0788.05067
[6] Y. Hong, J. Shu and K. Fang: A sharp upper bound of the spectral radius of graphs. J. Combinatorial Theory Ser. B 81 (2001), 177–183. DOI 10.1006/jctb.2000.1997 | MR 1814902
[7] R. Merris: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197-198 (1994), 143–176. MR 1275613 | Zbl 0802.05053
[8] R. Stanley: A bound on the spectral radius of graphs with $e$ edges. Linear Algebra Appl. 87 (1987), 267–269. DOI 10.1016/0024-3795(87)90172-8 | MR 0878683 | Zbl 0617.05045
[9] J. Shu, Y. Hong and W. Kai: A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph. Linear Algebra Appl. 347 (2002), 123–129. MR 1899886
[10] V. Nikiforov: Some inequalities for the largest eigenvalue of a graph. Combin. Probab. Comput. 11 (2002), 179–189. DOI 10.1017/S0963548301004928 | MR 1888908 | Zbl 1005.05029
[11] X. Zhang and J. Li: On the $k$-th largest eigenvalue of the Laplacian matrix of a graph. Acta Mathematicae Applicatae Sinica 17 (2001), 183–190. DOI 10.1007/BF02669571 | MR 1877099
Search
Partner of
