9
$\begingroup$

I am stuck at the following :

Let $G$ be a graph and $A$ is its adjacency matrix. Let the eigenvalues of $A$ be $\lambda_1\le \lambda_2\leq \cdots \leq \lambda_n$.

If we remove some edges from the graph $G$ and form the graph $H$ keeping the number of vertices same, is there any result how the smallest eigenvalue of $H$ is related to the smallest eigenvalue of $G$?

I know Cauchy Interlacing Theorem which gives the relation between eigenvalues of a graph and its induced subgraph when some vertices are removed.

I want to know what happens when edges are removed keeping the number of vertices same. Can someone help please?

The question stands as:

Let $G$ be a graph and $A_G$ is its adjacency matrix. Let the eigenvalues of $A_G$ be $\lambda_1\le \lambda_2\leq \cdots \leq \lambda_n$.

Let $H$ be a subgraph of $G$ which has $n$ vertices as $G$ but some edges have been removed from $G$ to form $H$.$A_H$ is its adjacency matrix.

Let the eigenvalues of $A_H$ be $\mu_1\le \mu_2\leq \cdots \leq \mu_n$.

Is $\mu_1\ge \lambda_1$ or $\mu_1\le \lambda_1$?

If someone can give any reference like book or paper , I will be grateful.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
16
$\begingroup$

The smallest eigenvalue can go up or down when an edge is removed.

For "down": $G=K_n$ for $n\ge 3$.

For "up": Take $K_n$ for $n\ge 1$ and append a new vertex attached to a single vertex of the original $n$ vertices. Now removing the new edge makes the smallest eigenvalue go up.

Both of these follow from the fact that the smallest eigenvalue of a connected graph with $n\ge 2$ vertices is $\le -1$ with equality iff the graph is complete.

It has something to do with whether the two corresponding eigenvector entries have the same or opposite sign, but I don't know if that relationship can be made precise.

Improve this answer
$\endgroup$
3
$\begingroup$

Here's a statement from the book "Spectra of Graphs" by Brouwer and Haemers concerning the largest eigenvalue of the adjacency matrix. It implies that $\lambda_n \geq \mu_n$.

Proposition 3.1.1 The value of the largest eigenvalue of a graph does not increase when vertices or edges are removed.

Improve this answer
$\endgroup$
1
  • $\begingroup$ But my question is about the smallest eigenvalue $\endgroup$
    – Charlotte
    Commented Jan 29, 2020 at 8:44
2
$\begingroup$

This might be helpful, from Eigenvalues and structures of graphs

Improve this answer
$\endgroup$
3
  • $\begingroup$ The result gives $0\le \theta_0\leq \lambda_1$ but I want to know how is $\lambda_0$ related to $\theta_0$ $\endgroup$
    – Charlotte
    Commented Jan 29, 2020 at 7:36
  • $\begingroup$ Is my question clear? $\endgroup$
    – Charlotte
    Commented Jan 29, 2020 at 7:36
  • 3
    $\begingroup$ This thm is for Laplacian eigenvalues, not adjacency-matrix eigenvalues. $\endgroup$
    – Brendan McKay
    Commented Jan 29, 2020 at 9:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .