Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.