Note on deleting a vertex and weak interlacing of the Laplacian spectrum Academic Article uri icon

abstract

  • 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≤ λv i≤ λi+ 1, where λi is the ith smallest eigenvalues of the Laplacian of the original graph and λv i is the ith smallest eigenvalues of the Laplacian of the graph G [V− v]; ie, 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

publication date

  • January 1, 2007