1
$\begingroup$

I am looking for upper bounds on the second largest eigenvalue, $\lambda_2(G)$ of a given graph $G$, with respect to minimum/maximum degrees of the graph. I looked around for some existing bounds most I found were with respect to the order of $G$.

Can anyone point me to something?

$\endgroup$
3
$\begingroup$

There exists arbitrarily large $d$-regular graphs with a cut edge. A direct inspection shows that the expansion tends to $0$. By the Cheeger inequality, $λ_2$ is arbitrarily close to $d=λ_1$.

There could be no bounds except $λ_2(G)<λ_1(G)$; in other words, $λ_2(G)$ can be arbitrarily close to $λ_1(G)$.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

If $G$ is a d-regular graph, then the second-largest eigenvalue of $A(G)$ is at least $2\sqrt{d-1} + o(1)$, where the $o(1)$ term goes to 0 as the number of vertices gets large.

If the number of vertices isn't much larger than $d$ then the second-largest eigenvalue can be much smaller. If $G$ is a complete graph on $d$ vertices where each vertex is adjacent to itself, then the second-largest eigenvalue of $A(G)$ is 0.

An upper bound for the second-largest eigenvalue is $d$ itself (if $G$ is $d$-regular but not connected).

ETA: I can add a bit more to my answer. The second-largest eigenvalue f a $d$-regular graph gives some sort of measure as far as the expansion of the graph i.e., how many vertices need to be cut to disconnect a large set of vertices from the rest of the graph. A $d$-regular graph that is disconnected will have $d$ as an eigenvalue with multiplicity at least 2. A d-regular connected graph with a cut vertex that bisects the graph nearly in half, will have a second-largest eigenvalue quite close to $d$ something like $d-O(1/n)$ where $n$ is the number of vertices. A $d$-regular expander where $d$ is $\theta(1)$ will have the second-largest eigenvalue no larger than $1-\epsilon)d$ for some $\epsilon \in \theta(1)$.

| cite | improve this answer | |
$\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.