4
$\begingroup$

I came across a Chinese reference in the paper "On the spectral radius of trees with fixed diameter" by Guo and Shao. The attribute the following to Q. Li, K.Q. Feng in: "On the largest eigenvalue of graphs", Acta Math. Appl. Sinica 2 (1979) 167–175.

Let $\lambda_1(H)$ be the spectral radius of the adjacency matrix of the graph H.

Let $G$ be a connected graph, and let $G'$ be a proper subgraph of $G$. Then $\lambda_1(G)>\lambda_1(G')$.

1) Is there a trivial argument of this using interlacing or is something more sophisticated needed here.

2) Is this also true for the Laplacian spectral radius. I assume if there is an interlacing argument this will be trivial.

$\endgroup$
1
  • $\begingroup$ 1) is Proposition 1.3.10 in Cvetković, Rowlinson & Simić, An Introduction to the Theory of Graph Spectra. $\endgroup$ Oct 20, 2014 at 12:31

3 Answers 3

8
$\begingroup$

Here is a simple proof. Without loss of generality, $G'$ is obtained from $G$ by deleting some edges (and keeping all vertices). Let $A$ and $A'$ denote the adjacency matrices of $G$ and $G'$, respectively, and let $x'$ be an eigenvector of $A'$, belonging to the eigenvalue $\lambda_1(G')$, such that all coordinates of $x'$ are non-negative. We have then $$ \lambda_1(G') = \frac{\langle x',A'x'\rangle}{\|x'\|^2} \le \frac{\langle x',Ax'\rangle}{\|x'\|^2} \le \sup_{x\ne 0} \frac{\langle x,Ax\rangle}{\|x\|^2} = \lambda_1(G); $$ indeed, if all coordinates of $x'$ are strictly positive, then the first inequality is strict, and if $x'$ has zero coordinates, then the second inequality is strict (by Perron-Frobenius, which says that the supremum is attained on a vector with all coordinates distinct from $0$).

The largest Laplacian eigenvalue (which, of course, is equal to the Laplacian spectral radius) can be dealt with in a similar manner. Suppose that $G'$ is obtained from $G$ by deleting some edges, and let $E$ and $E'$ be the edge sets of $G$ and $G'$, respectively. Furthermore, denote by $\mu_n(G)$ and $\mu_n(G')$ the largest Laplacian eigenvalues of $G$ and $G'$, and fix an eigenvector $x'$ of $G'$, belonging to the eigenvalue $\mu_n(G')$. Indexing coordinates by the vertices of $G$, we have

$$ \mu_n(G') = \frac{\sum_{(u,v)\in E'} (x'_u-x'_v)^2}{\|x'\|^2} \le \frac{\sum_{(u,v)\in E} (x'_u-x'_v)^2}{\|x'\|^2} \le \sup_{x\ne 0} \frac{\sum_{(u,v)\in E} (x_u-x_v)^2}{\|x\|^2} = \mu_n(G). $$

Notice that the inequality may fail to be strict in the Laplacian case; say, $\mu_3(K_3)=\mu_3(P_3)=3$.

$\endgroup$
0
3
$\begingroup$

There is a pretty straightforward counting argument which I give as Lemma 6 here. I don't think it is the standard argument, though.

$\endgroup$
0
$\begingroup$

It's an obvious consequence of part (b) of Corollary 1.5 on p.27 in Berman & Plemmons - a standard reference on nonnegative matrices.

$\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.