10
$\begingroup$

For two regular graphs $G$ and $H$, it is possible for them to share the same adjacent spectrum and the same laplacian spectrum. While, on the other hand, is it possible to have two non-regular graphs $G$ and $H$, which share the same adjacent spectrum and the same laplacian spectrum? Any comments or references would be greatly appreciated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
15
$\begingroup$

Yes, Brendan McKay showed that almost all trees have mates that are simultaneously cospectral in both adjacency and Laplacian spectra. And more.

http://users.cecs.anu.edu.au/~bdm/papers/SpectralTrees.pdf

Edit: I wondered briefly what the smallest pair of such trees would be, and a few minutes of Sage told me that there are two on 11 vertices.

And here they are (for some reason I am having difficulty with the image uploader):

enter image description here

enter image description here

Improve this answer
$\endgroup$

You must log in to answer this question.

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