| Title:
|
On the bounds of Laplacian eigenvalues of $k$-connected graphs (English) |
| Author:
|
Chen, Xiaodan |
| Author:
|
Hou, Yaoping |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
65 |
| Issue:
|
3 |
| Year:
|
2015 |
| Pages:
|
701-712 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
$k$-connected graph |
| Keyword:
|
non-regular graph |
| Keyword:
|
algebraic connectivity |
| Keyword:
|
Laplacian spectral radius |
| Keyword:
|
maximum degree |
| MSC:
|
05C50 |
| MSC:
|
15A18 |
| idZBL:
|
Zbl 06537687 |
| idMR:
|
MR3407600 |
| DOI:
|
10.1007/s10587-015-0203-4 |
| . |
| Date available:
|
2015-10-04T18:10:13Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144438 |
| . |
| Reference:
|
[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). Zbl 1211.05002, MR 2571608 |
| Reference:
|
[2] Abreu, N. M. M. de: Old and new results on algebraic connectivity of graphs.Linear Algebra Appl. 423 (2007), 53-73. Zbl 1115.05056, MR 2312323, 10.1016/j.laa.2006.08.017 |
| Reference:
|
[3] Diestel, R.: Graph Theory.Graduate Texts in Mathematics 173 Springer, Berlin (2010). Zbl 1209.00049, MR 2744811 |
| Reference:
|
[4] Fiedler, M.: Algebraic connectivity of graphs.Czech. Math. J. 23 (1973), 298-305. Zbl 0265.05119, MR 0318007 |
| Reference:
|
[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. Zbl 0991.05071, MR 1873608 |
| Reference:
|
[6] Li, J., Shiu, W. C., Chang, A.: The Laplacian spectral radius of graphs.Czech. Math. J. 60 (2010), 835-847. Zbl 1224.05304, MR 2672418, 10.1007/s10587-010-0052-0 |
| Reference:
|
[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. Zbl 1106.05064, MR 2278217 |
| Reference:
|
[8] Merris, R.: Laplacian matrices of graphs: A survey.Linear Algebra Appl. 197-198 (1994), 143-176. Zbl 0802.05053, MR 1275613 |
| Reference:
|
[9] Mohar, B.: Eigenvalues, diameter, and mean distance in graphs.Graphs Comb. 7 (1991), 53-64. Zbl 0771.05063, MR 1105467, 10.1007/BF01789463 |
| Reference:
|
[10] Ning, W., Li, H., Lu, M.: On the signless Laplacian spectral radius of irregular graphs.Linear Algebra Appl. 438 (2013), 2280-2288. Zbl 1258.05074, MR 3005290, 10.1016/j.laa.2012.10.024 |
| Reference:
|
[11] Shi, L.: Bounds on the ({L}aplacian) spectral radius of graphs.Linear Algebra Appl. 422 (2007), 755-770. Zbl 1113.05065, MR 2305155, 10.1016/j.laa.2006.12.003 |
| Reference:
|
[12] Zhang, X.-D., Luo, R.: The spectral radius of triangle-free graphs.Australas. J. Comb. (electronic only) 26 (2002), 33-39. Zbl 1008.05089, MR 1918140 |
| . |
