A363065 Number of Laplacian integral graphs on n vertices.

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

Offset

1,2

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).

Since a graph is Laplacian integral if and only if its connected components are Laplacian integral, the number of Laplacian integral graphs can be computed from the number of connected Laplacian integral graphs (A363064) via a(n) = Sum_{p} Product_{k=1..n} binomial(A363064(k)+f(p,k)-1,f(p,k)), where the outer sum is over all partitions p of n (A000041) and f(p,k) is the number of parts of p that equal k. - Nathaniel Johnston, May 16 2026

Links

Table of n, a(n) for n=1..11.

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

Example

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.

Crossrefs

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

Sequence in context: A029893 A372123 A148089 * A200743 A061055 A060776

Adjacent sequences: A363062 A363063 A363064 * A363066 A363067 A363068

Keyword

nonn,more

Author

Nathaniel Johnston, May 16 2023

Extensions

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

a(11) from Nathaniel Johnston, May 16 2026

Status

approved