On the bounds of Laplacian eigenvalues of k -connected graphs

Xiaodan Chen; Yaoping Hou

Czechoslovak Mathematical Journal (2015)

  • Volume: 65, Issue: 3, page 701-712
  • ISSN: 0011-4642

Abstract

top
Let μ n - 1 ( G ) be the algebraic connectivity, and let μ 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 μ n - 1 ( G ) ≥ 2 n k 2 ( n ( n - 1 ) - 2 m ) ( n + k - 2 ) + 2 k 2 , with equality if and only if G is the complete graph K n or K n - e . Moreover, if G is non-regular, then μ 1 ( G ) < 2 Δ - 2 ( n Δ - 2 m ) k 2 2 ( n Δ - 2 m ) ( n 2 - 2 n + 2 k ) + n k 2 , where Δ stands for the maximum degree of G . Remark that in some cases, these two inequalities improve some previously known results.

How to cite

top

Chen, Xiaodan, and Hou, Yaoping. "On the bounds of Laplacian eigenvalues of $k$-connected graphs." Czechoslovak Mathematical Journal 65.3 (2015): 701-712. <http://eudml.org/doc/271824>.

@article{Chen2015,
abstract = {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)\ge \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.},
author = {Chen, Xiaodan, Hou, Yaoping},
journal = {Czechoslovak Mathematical Journal},
keywords = {$k$-connected graph; non-regular graph; algebraic connectivity; Laplacian spectral radius; maximum degree},
language = {eng},
number = {3},
pages = {701-712},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On the bounds of Laplacian eigenvalues of $k$-connected graphs},
url = {http://eudml.org/doc/271824},
volume = {65},
year = {2015},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 3
SP - 701
EP - 712
AB - 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)\ge \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.
LA - eng
KW - $k$-connected graph; non-regular graph; algebraic connectivity; Laplacian spectral radius; maximum degree
UR - http://eudml.org/doc/271824
ER -

References

top
  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). (2010) Zbl1211.05002MR2571608
  2. Abreu, N. M. M. de, 10.1016/j.laa.2006.08.017, Linear Algebra Appl. 423 (2007), 53-73. (2007) Zbl1115.05056MR2312323DOI10.1016/j.laa.2006.08.017
  3. Diestel, R., Graph Theory, Graduate Texts in Mathematics 173 Springer, Berlin (2010). (2010) Zbl1209.00049MR2744811
  4. Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298-305. (1973) Zbl0265.05119MR0318007
  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. (2002) Zbl0991.05071MR1873608
  6. Li, J., Shiu, W. C., Chang, A., 10.1007/s10587-010-0052-0, Czech. Math. J. 60 (2010), 835-847. (2010) Zbl1224.05304MR2672418DOI10.1007/s10587-010-0052-0
  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. (2007) Zbl1106.05064MR2278217
  8. Merris, R., Laplacian matrices of graphs: A survey, Linear Algebra Appl. 197-198 (1994), 143-176. (1994) Zbl0802.05053MR1275613
  9. Mohar, B., 10.1007/BF01789463, Graphs Comb. 7 (1991), 53-64. (1991) Zbl0771.05063MR1105467DOI10.1007/BF01789463
  10. Ning, W., Li, H., Lu, M., 10.1016/j.laa.2012.10.024, Linear Algebra Appl. 438 (2013), 2280-2288. (2013) Zbl1258.05074MR3005290DOI10.1016/j.laa.2012.10.024
  11. Shi, L., 10.1016/j.laa.2006.12.003, Linear Algebra Appl. 422 (2007), 755-770. (2007) Zbl1113.05065MR2305155DOI10.1016/j.laa.2006.12.003
  12. Zhang, X.-D., Luo, R., The spectral radius of triangle-free graphs, Australas. J. Comb. (electronic only) 26 (2002), 33-39. (2002) Zbl1008.05089MR1918140

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.