Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
$k$-connected graph; non-regular graph; algebraic connectivity; Laplacian spectral radius; maximum degree
$k$-connected graph; non-regular graph; algebraic connectivity; Laplacian spectral radius; maximum degree
Summary:
Let $\mu _{n-1}(G)$ be the algebraic connectivity, and let $\mu _{1}(G)$ be the Laplacian spectral radius of a $k$-connected graph $G$ with $n$ vertices and $m$ edges. In this paper, we prove that \begin {equation*} \mu _{n-1}(G)\geq \frac {2nk^2}{(n(n-1)-2m)(n+k-2)+2k^2}, \end {equation*} with equality if and only if $G$ is the complete graph $K_n$ or $K_{n}-e$. Moreover, if $G$ is non-regular, then \begin {equation*} \mu _1(G)<2\Delta -\frac {2(n\Delta -2m)k^2}{2(n\Delta -2m)(n^2-2n+2k)+nk^2}, \end {equation*} where $\Delta $ stands for the maximum degree of $G$. Remark that in some cases, these two inequalities improve some previously known results.
References:
[1] Cvetković, D., Rowlinson, P., Simić, S.: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts 75 Cambridge University Press, Cambridge (2010). MR 2571608 | Zbl 1211.05002
[2] Abreu, N. M. M. de: Old and new results on algebraic connectivity of graphs. Linear Algebra Appl. 423 (2007), 53-73. DOI 10.1016/j.laa.2006.08.017 | MR 2312323 | Zbl 1115.05056
[3] Diestel, R.: Graph Theory. Graduate Texts in Mathematics 173 Springer, Berlin (2010). MR 2744811 | Zbl 1209.00049
[4] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. MR 0318007 | Zbl 0265.05119
[5] Kirkland, S. J., Molitierno, J. J., Neumann, M., Shader, B. L.: On graphs with equal algebraic and vertex connectivity. Linear Algebra Appl. 341 (2002), 45-56. MR 1873608 | Zbl 0991.05071
[6] Li, J., Shiu, W. C., Chang, A.: The Laplacian spectral radius of graphs. Czech. Math. J. 60 (2010), 835-847. DOI 10.1007/s10587-010-0052-0 | MR 2672418 | Zbl 1224.05304
[7] Lu, M., Zhang, L.-Z., Tian, F.: Lower bounds of the Laplacian spectrum of graphs based on diameter. Linear Algebra Appl. 420 (2007), 400-406. MR 2278217 | Zbl 1106.05064
[8] Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. MR 1275613 | Zbl 0802.05053
[9] Mohar, B.: Eigenvalues, diameter, and mean distance in graphs. Graphs Comb. 7 (1991), 53-64. DOI 10.1007/BF01789463 | MR 1105467 | Zbl 0771.05063
[10] Ning, W., Li, H., Lu, M.: On the signless Laplacian spectral radius of irregular graphs. Linear Algebra Appl. 438 (2013), 2280-2288. DOI 10.1016/j.laa.2012.10.024 | MR 3005290 | Zbl 1258.05074
[11] Shi, L.: Bounds on the ({L}aplacian) spectral radius of graphs. Linear Algebra Appl. 422 (2007), 755-770. DOI 10.1016/j.laa.2006.12.003 | MR 2305155 | Zbl 1113.05065
[12] Zhang, X.-D., Luo, R.: The spectral radius of triangle-free graphs. Australas. J. Comb. (electronic only) 26 (2002), 33-39. MR 1918140 | Zbl 1008.05089
Search
Partner of
