login
Number of Laplacian integral graphs on n vertices.
3

%I #14 May 26 2023 11:29:22

%S 1,2,4,10,24,70,188,553,1721,5716

%N Number of Laplacian integral graphs on n vertices.

%C A (simple, undirected) graph is called Laplacian integral if all eigenvalues of its Laplacian matrix are integers. The corresponding sequence that uses the adjacency matrix instead of the Laplacian matrix is A077027.

%C Since every cograph is Laplacian integral, a(n) >= A000084(n).

%H R. Grone and R. Merris, <a href="https://doi.org/10.1016/j.laa.2007.09.025">Indecomposable Laplacian integral graphs</a>, Linear Algebra and its Applications, 428 (2008), 1565-1570.

%e For n <= 3, all graphs are Laplacian integral, so a(n) = A000088(n) when n <= 3.

%e There is exactly one graph on 4 vertices that is not Laplacian integral: the path P_4, which has Laplacian matrix

%e 1 -1 0 0

%e -1 2 -1 0

%e 0 -1 2 -1

%e 0 0 -1 1

%e which has eigenvalues 0, 2, 2-sqrt(2), and 2+sqrt(2), which are not all integers.

%Y Cf. A000084, A000088, A077027, A363064 (connected graphs only).

%K nonn,more

%O 1,2

%A _Nathaniel Johnston_, May 16 2023

%E a(10) from _M. A. Achterberg_, May 26 2023