Note on deleting a vertex and weak interlacing of the Laplacian spectrum
Main Article Content
Abstract
The question of what happens to the eigenvalues of the Laplacian of a graph when
we delete a vertex is addressed. It is shown that
λi − 1 ≤ λvi ≤ λi+1,
where λi is the ith smallest eigenvalues of the Laplacian of the original graph and λvi is the ith smallest eigenvalues of the Laplacian of the graph G[V −v]; i.e., the graph obtained after removing the vertex v. It is shown that the average number of leaves in a random spanning tree F(G) > 2|E|e-1/α / λn , if λ2 > αn.
Article Details
Issue
Section
Article