login
Number of connected Laplacian integral graphs on n vertices.
3

%I #15 May 26 2023 11:45:21

%S 1,1,2,5,12,37,94,280,912,3164

%N Number of connected 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 A064731.

%C Since every cograph is Laplacian integral, a(n) >= A000669(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 connected graphs are Laplacian integral, so a(n) = A001349(n) when n <= 3.

%e There is exactly one connected 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. A000669, A001349, A064731, A363065 (include disconnected graphs).

%K nonn,hard,more

%O 1,3

%A _Nathaniel Johnston_, May 16 2023

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