|
|
A363064
|
|
Number of connected Laplacian integral graphs on n vertices.
|
|
3
|
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|