2
$\begingroup$

Two graphs are isomorphic if they just have a different labeling for their vertices i.e. if $A$ and $B$ are their adjacency matrices, then, for some permutation matrix $P$, $PAP^T = B$.

Two graphs are isospectral, if they have the same set of eigenvalues.

Question : Are isomorphic graphs necessarily isospectral?

$\endgroup$
5
$\begingroup$

The eigenvalues follow from the characteristic equation, so

\begin{align*} \det(B-\lambda I)&= \det(PAP^T-\lambda I)\\ &= \det(PAP^T-P(\lambda I) P^T)\\ &= \det(P(A-\lambda I)P^T)\\ &= \det(P)\det(A-\lambda I)\det(P^T)\\ &= \det(A-\lambda I) \end{align*}

so the two adjacency graphs have the same characteristic matrix and therefore the same eigenvalues. Note I used the fact that $PP^T=I$ and $\det(P)=\det(P^T)=1$

$\endgroup$
2
$\begingroup$

two isomorphic graphs are isospectral since they have the same number of cycles and nodes. quasi-isospectral graphs were also classified by Bisson and Tsemo by using closed models.

http://intlpress.com/site/pub/files/_fulltext/journals/hha/2009/0011/0001/HHA-2009-0011-0001-a008.pdf

$\endgroup$
2
$\begingroup$

Alternate proof in addition to the ones already mentioned :

Let $B = PAP^T$, then if $v$ was the eigenvector of $A$ corresponding to the eigenvalue $\lambda$ : $$B(Pv) = (PAP^T)(Pv) = PAv = \lambda Pv$$ Thus, $\lambda$ is also a eigenvalue of $B$.

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