Post

New preprint with Sarah Plosker and my student, Luis Varona: "Enumeration of Laplacian integral and {-1,0,1}-diagonalizable graphs" (description in replies) arxiv.org/abs/2607.06336

arxiv.orgEnumeration of Laplacian integral and {-1,0,1}-diagonalizable graphsA 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 entri...

Nathaniel Johnston

@njohnston.ca

8 July

Luis did some great computational work that led us to conjecture that every order-n Laplacian integral graph, when n is prime, has disconnected complement. We ended up proving this conjecture (Theorem 1 in the paper, which has a surprisingly simple proof).

Nathaniel Johnston

@njohnston.ca

8 July

Luis's computational results generated all Laplacian integral graphs up to order 12. Theorem 1 then makes it straightforward to generate all Laplacian integral graphs on order 13 as well.

Nathaniel Johnston

@njohnston.ca

Luis's numerics also suggested some other conjectures. Some of these conjectures were true (such as what is now Theorem 5 in the paper) and some were not. One of the not-true conjectures was that if n is prime then the only connected regular {-1,0,1}-diagonalizable graph is the complete graph K_n.

8/7/26, 1:36 pm0 reposts0 likes

Nathaniel Johnston

@njohnston.ca

8 July

In the process of trying to prove this conjecture, we showed that K_n is indeed the only such graph for n prime when n <= 29. However, for n >= 31, there are others (Table 3).