|
%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
|
