4
$\begingroup$

Let G be a connected undirected graph and G\e be a graph obtained by removing a random link e from the graph G. Let $\lambda_1(A(G))$ be the largest eigenvalue of the adjacency matrix of graph G. Is $\lambda_1(A(G))-\lambda_1(A(G\backslash e)) \geq 0$? in other words, deleting a link will never increase the largest eigenvalue of the (adjacency matrix of) resulting graph.

$\endgroup$

2 Answers 2

5
$\begingroup$

This (i.e. the non-increase of $\lambda_1$ w.r.t. edge removal) follows from the fact that $$\lambda_1=\max_{x\geq 0,\|x\|=1} x^\top A x.$$

The latter is a consequence of the characterisation of $\lambda_1$ as the maximum Rayleigh quotient and the positivity of the corr. eigenvector.

$\endgroup$
1
$\begingroup$

I write this as an answer since I need some vote to break the symmetry of my reputation. I hope I never fall down to the other symmetry.

The answer of your question is yes. Actually you can see the Proposition $1.3.10$ of

"An introduction to the theory of graph spectra".

Maybe you do not have this book, the proof is as follow:

Let $x=(x_1,x_2,\ldots ,x_n)^t$ be a non-negative unit eigenvector of $G - uv$ corresponding to $\lambda_1(G-uv)$. Then $$\lambda_1(G-uv)= x^tA(G-uv)x < x^tA(G)x <\lambda_1(G). $$

If $\lambda_1(G-uv)=\lambda_1(G)$ then $x$ is the principal eigenvector of $G$ and hence has no zero entries. Now $x^tA(G-uv)x=x^tA(G)x- 2x_ux_v < \lambda_1(G-uv)$, a contradiction.

I just copied the proof. You can see the inequality is strictly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.