2
$\begingroup$

Let $L$ be the Laplacian matrix for a simple graph $G$ of $n$ vertices, and $\lambda_0,\ldots,\lambda_{n-1}$ its $n$ eigenvalues.

Q. What is the cardinality of the class of $n$-vertex graphs $\cal G$, that each have the same Laplacian eigenvalues as $G$? Presumably $G$ is not uniquely determined by its eigenvalues. What are examples of pairs or clusters of graphs with the same eigenvalues?

The smallest and second-smallest eigenvalues are the spectral gap and algebraic connectivity of $G$ respectively, and the third-smallest relates to partitioning $G$ into pieces. See the 2015 MO question, Spectral theory of graph Laplacian besides $\lambda_2$, for further properties of the eigenvalues.

I also wonder if the new result that eigenvectors are determined by eigenvalues might play a role here.

  • Natalie Wolchover. "Neutrinos Lead to Unexpected Discovery in Basic Math." Quanta. 2019.

  • Peter B. Denton, Stephen J. Parke, Terence Tao, Xining Zhang. "Eigenvectors from Eigenvalues." arXiv abstract. 2019.

  • Van Mieghem, Piet. "Graph eigenvectors, fundamental weights and centrality metrics for nodes in networks." arXiv abstract. 2014.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ W.r.t. your last line: it seems that the formula for computing eigenvectors from eigenvalues has been discovered before in the context of eigenvalues of graphs, see here: arxiv.org/abs/1401.4580. I found this link through the addendum to the quanta-article you link to, so perhaps you already knew this. $\endgroup$
    – Vincent
    Nov 20, 2019 at 14:46
  • $\begingroup$ @Vincent: Thanks, added Van Mieghem's preprint to the list. $\endgroup$
    – Joseph O'Rourke
    Nov 21, 2019 at 12:16
  • 3
    $\begingroup$ trackback: findstat.org/St001496, in particular, for at most 5 vertices, there are no coincidences, for 6 vertices there are two pairs, and for 7 vertices there are also a few triplets with the same list of eigenvalues. $\endgroup$
    – Martin Rubey
    Nov 21, 2019 at 15:29
  • $\begingroup$ Thanks, @MartinRubey, for the calculation. Impressively concise code! $\endgroup$
    – Joseph O'Rourke
    Nov 21, 2019 at 15:51
  • $\begingroup$ Would it be interesting to consider graphs with the same set of eigenvalues, too? (There are much more coincidences in this case.) $\endgroup$
    – Martin Rubey
    Nov 21, 2019 at 16:24

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.