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.

Improve this question
$\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
    Commented Sep 11, 2011 at 22:20

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .