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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Aug 25, 2014 at 20:49
$\begingroup$
$\endgroup$
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.
