Deleting vertices and interlacing Laplacian eigenvalues

Abstract

The authors obtain an interlacing relation between the Laplacian spectra of a graph G and its subgraph G-U, which is obtained from G by deleting all the vertices in the vertex subset U together with their incident edges. Also, some applications of this interlacing property are explored and this interlacing property is extended to the edge weighted graphs.

Keywords

Interlacing inequality / Eigenvalue / Spectrum / Laplacian matrix

References

[1] Brouwer A. E., Haemers W. H.. A lower bound for the Laplacian eigenvalues of a graph—Proof of a conjecture by Guo. Linear Algebra Appl., 2008, 429: 2131-2135

[2] Fiedler M.. Algebraic connectivity of graphs. Czech. Math. J., 1973, 23: 298-305

[3] Godsil C., Royle G.. Algebraic Graph Theory, 2001, New York: Springer-Verlag

[4] Grone R., Merris R., Sunder V. S.. The Laplacian spectrum of a graph. SIAM J. Matrix Anal. Appl., 1990, 11(2): 218-238

[5] Grone R., Merris R.. The Laplacian spectrum of a graph II. SIAM J. Discrete Math., 1994, 7: 221-229

[6] Guo J. M.. On the third largest Laplacian eigenvalue of a graph. Linear and Multilinear Algebra, 2007, 55: 93-102

[7] Horn R. A., Johnson C. R.. Matrix Analysis, 1985, Cambridge: Cambridge University Press

[8] Lotker Z.. Note on deleting a vertex and weak interlacing of the Laplacian spectrum. Electronic J. Linear Algebra, 2007, 16: 68-72

[9] Mohar B.. The Laplacian spectrum of graphs. Graph Theory, Combin., Appl., 1991, 2: 871-898