5
$\begingroup$

Suppose I have some $d$-regular graph $G$. Let $\lambda = \max\{\lambda_2(G), |\lambda_n(G)|\}$ be the second largest eigenvalue of the adjacency matrix of $G$. Now take $\tilde{G}$, the suspension of $G$, obtained by adding a new vertex $v$ and connecting $v$ to all vertices of $G$. Is it true that $\lambda(\tilde{G}) \leq \lambda(G)$? (or more generally, is it true if instead of suspending with one vertex we suspend with a clique of size $n$)

The intuition is that $\tilde{G}$ should exhibit better mixing (hence, smaller $\lambda$), since it's easier for a random walk to get from one vertex to any other.

$\endgroup$
1
  • $\begingroup$ Shouldn't you be looking at the Laplacian, rather than the adjacency matrix? For non-regular graphs I'm not sure if the second largest eigenvalue is the thing that controls mixing. Also, the operation you're interested in seems more like taking the cone over $G$, rather than a suspension. $\endgroup$
    – Alon Amit
    Sep 11, 2011 at 22:20

1 Answer 1

6
$\begingroup$

The eigenvalues of $G$ determine the eigenvalues of $\tilde G$ in the regular case. If I calculated correctly, just replace the eigenvalue $d$ by the two zeros of $x^2-dx-n$, and keep the other eigenvalues the same. This is for the adjacency matrix. I agree with Alon that you might be looking at the wrong matrix, and I would also call this the cone of $G$.

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