Geodesic
On the bounds of Laplacian eigenvalues of $k$-connected graphs
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 3, pp. 701-712 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-015-0203-4
Classification : 05C50, 15A18
Keywords: $k$-connected graph; non-regular graph; algebraic connectivity; Laplacian spectral radius; maximum degree 
@article{10_1007_s10587_015_0203_4,
     author = {Chen, Xiaodan and Hou, Yaoping},
     title = {On the bounds of {Laplacian} eigenvalues of $k$-connected graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {701--712},
     year = {2015},
     volume = {65},
     number = {3},
     doi = {10.1007/s10587-015-0203-4},
     mrnumber = {3407600},
     zbl = {06537687},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0203-4/}
}
TY  - JOUR
AU  - Chen, Xiaodan
AU  - Hou, Yaoping
TI  - On the bounds of Laplacian eigenvalues of $k$-connected graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2015
SP  - 701
EP  - 712
VL  - 65
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0203-4/
DO  - 10.1007/s10587-015-0203-4
LA  - en
ID  - 10_1007_s10587_015_0203_4
ER  - 
%0 Journal Article
%A Chen, Xiaodan
%A Hou, Yaoping
%T On the bounds of Laplacian eigenvalues of $k$-connected graphs
%J Czechoslovak Mathematical Journal
%D 2015
%P 701-712
%V 65
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0203-4/
%R 10.1007/s10587-015-0203-4
%G en
%F 10_1007_s10587_015_0203_4
Chen, Xiaodan; Hou, Yaoping. On the bounds of Laplacian eigenvalues of $k$-connected graphs. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 3, pp. 701-712. doi: 10.1007/s10587-015-0203-4

[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 | Zbl

[2] Abreu, N. M. M. de: Old and new results on algebraic connectivity of graphs. Linear Algebra Appl. 423 (2007), 53-73. | DOI | MR | Zbl

[3] Diestel, R.: Graph Theory. Graduate Texts in Mathematics 173 Springer, Berlin (2010). | MR | Zbl

[4] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. | MR | Zbl

[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 | Zbl

[6] Li, J., Shiu, W. C., Chang, A.: The Laplacian spectral radius of graphs. Czech. Math. J. 60 (2010), 835-847. | DOI | MR | Zbl

[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 | Zbl

[8] Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. | MR | Zbl

[9] Mohar, B.: Eigenvalues, diameter, and mean distance in graphs. Graphs Comb. 7 (1991), 53-64. | DOI | MR | Zbl

[10] Ning, W., Li, H., Lu, M.: On the signless Laplacian spectral radius of irregular graphs. Linear Algebra Appl. 438 (2013), 2280-2288. | DOI | MR | Zbl

[11] Shi, L.: Bounds on the ({L}aplacian) spectral radius of graphs. Linear Algebra Appl. 422 (2007), 755-770. | DOI | MR | Zbl

[12] Zhang, X.-D., Luo, R.: The spectral radius of triangle-free graphs. Australas. J. Comb. (electronic only) 26 (2002), 33-39. | MR | Zbl

Cité par Sources :