Menu
Given a graph \( G \), the adjacency matrix \( A(G) \), the standard Laplacian \( L(G) \), and the normalized Laplacian \( \mathcal{L}(G) \) have been studied intensively. In this paper, interlacing inequalities are given for each of these three matrices under the two operations of removing an edge or a vertex from \( G \). Examples are given to show that the inequalities are the best possible of their type. In addition, an interlacing result is proven for the adjacency matrix when two vertices of \( G \) are contracted. Among the results given are the following.
Let \( G \) be a graph and let \( H \) be a graph obtained from \( G \) by removing an edge or a vertex of degree \( r \). Let \( \lambda_i \), \( i = 1, 2, \ldots, n \) be the eigenvalues associated with \( A(G) \), \( L(G) \), or \( \mathcal{L}(G) \) and let \( \theta_i \) be the eigenvalues associated with \( A(H) \), \( L(H) \), or \( \mathcal{L}(H) \), where both sets of eigenvalues are in nonincreasing order.
In the case of removing a vertex so that \( H = G – v \), for the normalized Laplacian we have \( \lambda_{i – r + 1} \geq \theta_i \geq \lambda_{i+r} \). For the standard Laplacian we have \( \lambda_i \geq \theta_i \geq \lambda_{i+r} \). In the case of removing an edge so that \( H = G – e \), where \( e \) is an edge incident on a vertex of degree \( 1 \), for the normalized Laplacian we have \( \lambda_i \geq \theta_i \geq \lambda_{i+1} \).