# Spectral radius of “almost” regular graph ?!

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!

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