MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Alon Amit Sep 11 '11 at 22:20

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

share|cite|improve this answer

Your Answer


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.