Butler, Steve

Interlacing for weighted graphs using the normalized Laplacian

Electron. J. Linear Algebra 16, 90-98, electronic only (2007)

Summary

Summary: The problem of relating the eigenvalues of the normalized Laplacian for a weighted graph G and G - H, for H a subgraph of G is considered. It is shown that these eigenvalues interlace and that the tightness of the interlacing is dependent on the number of nonisolated vertices of H. Weak coverings of a weighted graph are also defined and interlacing results for the normalized Laplacian for such a covering are given. In addition there is a discussion about interlacing for the Laplacian of directed graphs.

Mathematics Subject Classification

05C50, 15A42

Keywords/Phrases

Laplacian matrix, interlacing, directed Laplacian, weak coverings

Downloads