Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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