Enumeration of Laplacian integral and {-1,0,1}-diagonalizable graphs

Abstract:
A graph with Laplacian matrix \(L\) is called Laplacian integral if the eigenvalues of \(L\) are all integers, and it is called \(\{-1,0,1\}\)-diagonalizable if \(L\) has a full set of eigenvectors with entries from \(\{-1,0,1\}\). We herein develop a structure theorem for both Laplacian integral graphs and \(\{-1,0,1\}\)-diagonalizable graphs of prime order, and combine it with some novel computational techniques to characterize all such graphs for orders larger than was previously possible. For example, we enumerate all Laplacian integral and \(\{-1,0,1\}\)-diagonalizable graphs of order 13 or less, all \(\{-1,0,1\}\)-diagonalizable graphs of prime order 23 or less, all regular integral graphs of order 15 or less, and all regular \(\{-1,0,1\}\)-diagonalizable graphs of prime order 53 or less. As an immediate byproduct of our work, we show that the \(S_{n,n}\) conjecture for Laplacian integral graphs is true when \(n = 12\), thus making \(n = 16\) the smallest open case; additionally, we disprove two related conjectures regarding Laplacian spectra. We also establish an exponential lower bound on the number of connected \(\{-1,0,1\}\)-diagonalizable graphs of order \(n\), thus beating the previously best-known (subexponential) lower bound. Finally, we show that every bipartite \(\{-1,0,1\}\)-diagonalizable graph is regular (a fact that fails to generalize to Laplacian integral graphs).
Authors:

Download:

  • Preprint from arXiv:2607.06336 [math.CO]

Cite as:

  • N. Johnston, S. Plosker, and L. M. B. Varona. Enumeration of Laplacian integral and {-1,0,1}-diagonalizable graphs. E-print: arXiv:2607.06336 [math.CO], 2026.

Related papers: