4
$\begingroup$

The answer to this question could be trivial.

The Graph Let $G$ be graph formed of two $d$-regular connected components. That is, $G= H_1\cup H_2$, where $H_1$, and $H_2$ are $d$-regular and disjoint. Let $x\in H_1$ and $y\in H_2$. Let $G'= G+xy$, then $G'$ is connected graph. My question is:

Question: What is the largest positive eigenvalue of $G'$ ? Or $\lambda_1 (G') = ??$

Ideas:

-It is obvious that $\lambda_1 (G) = d$ with multiplicity 2 ( since it is formed of 2 $d$-regular connected components). But I have no idea how to estimate $\lambda_1$ when a single edge is added between $H_1$, and $H_2$.

-The interlacing theorem could help in commutating bound for the maximal eigenvalue.

Any idea will be useful!

$\endgroup$
2
+50
$\begingroup$

In your case, the interlacing result you mentioned is that $\lambda_1(G') \geq \lambda_2(G)=d$. For the other direction, Weyl's inequality (the triangle inequality for spectral radius) tells you $$\lambda_1(G') \leq \lambda_1(G) + \lambda_1(G-G')=d+1,$$ but I think we can say something stronger.

Suppose we have $$A'v = \lambda v $$ where $A'$ is the adjacency matrix of $G'$. Assume WLOG that $|v(x)| \geq |v(y)|$, and let $z$ be a vertex having maximal $|v(z)|$ among all vertices other than $x$ and $y$. Using the triangle inequality and the eigenvalue definition, we have $$\lambda |v(x)| = |(A' v) x | \leq \sum_{w \sim x} |v(w)| \leq |v(x)| + d |v(z)|$$ (the $d$ neighbors of $x$ in $H_1$ each contribute at most $|v(z)|$, and $y$ contributes at most $|v(x)|$). Similarly, $$\lambda |v(z)| = |(A' v) z| \leq \sum_{w \sim z} |v(w)| \leq |v(x)| + (d-1) |v(z)|$$

Let $v'=\left(\begin{array}{c} |v(x)| \\ |v(z)| \end{array}\right)$, and let $M=\left(\begin{array}{cc} 1 & d \\ 1 & d-1\end{array}\right)$. The above inequalities tell us $$0 \leq \lambda v' \leq M v'$$ in each coordinate, so we have $$\lambda ||v'|| \leq ||M v'|| \leq ||M|| ||v'|| = \frac{1}{2} (d+\sqrt{d^2+4}) ||v'||$$ So the spectral radius of $G'$ is at most $\frac{1}{2} (d+\sqrt{d^2+4})$. For large $d$ this is roughly $d+\frac{1}{d}$.

I have a feeling this may be well-known/classical, but don't have a reference.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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