login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A363064
Number of connected Laplacian integral graphs on n vertices.
3
1, 1, 2, 5, 12, 37, 94, 280, 912, 3164
OFFSET
1,3
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 A064731.
Since every cograph is Laplacian integral, a(n) >= A000669(n).
LINKS
R. Grone and R. Merris, Indecomposable Laplacian integral graphs, Linear Algebra and its Applications, 428 (2008), 1565-1570.
EXAMPLE
For n <= 3, all connected graphs are Laplacian integral, so a(n) = A001349(n) when n <= 3.
There is exactly one connected 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. A000669, A001349, A064731, A363065 (include disconnected graphs).
Sequence in context: A267398 A267399 A267400 * A052302 A280275 A009598
KEYWORD
nonn,hard,more
AUTHOR
Nathaniel Johnston, May 16 2023
EXTENSIONS
a(10) from M. A. Achterberg, May 26 2023
STATUS
approved