A363065 Number of Laplacian integral graphs on n vertices.

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

Offset: 1

Author

Nathaniel Johnston, May 16 2023

Keywords

• nonn
• more

Comments

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.

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

Examples

			For n <= 3, all graphs are Laplacian integral, so a(n) = A000088(n) when n <= 3.
There is exactly one graph on 4 vertices that is not Laplacian integral: the path P_4, which has Laplacian matrix
   1 -1  0  0
  -1  2 -1  0
   0 -1  2 -1
   0  0 -1  1
which has eigenvalues 0, 2, 2-sqrt(2), and 2+sqrt(2), which are not all integers.
		

Links

• R. Grone and R. Merris, Indecomposable Laplacian integral graphs, Linear Algebra and its Applications, 428 (2008), 1565-1570.

Crossrefs

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

Extensions

a(10) from M. A. Achterberg, May 26 2023