login
A331414
Number of integral free trees of n vertices.
0
1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 3, 0, 1, 0, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 3, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 2
OFFSET
0,18
COMMENTS
A tree (or graph) is integral when the roots of the characteristic polynomial of its adjacency matrix are all integers (so integer spectrum of that matrix).
Per Harary and Schwenk, a star comprising a vertex and n leaves around it has spectrum 0,+-sqrt(n). This is integral when n is a square, so a(n^2+1) >= 1. Brouwer made a computer search to find all integral trees up to 50 vertices, which gives values here to a(50), by reducing the search space with tests of Cauchy interlacing to eliminate branches.
REFERENCES
F. Harary and A. J. Schwenk, Which Graphs Have Integral Spectra?, in Graphs and Combinatorics, Lecture Notes in Mathematics 406, Springer-Verlag, Berlin, 1974.
LINKS
A. E. Brouwer, Small Integral Trees, preprint 2007.
A. E. Brouwer, Small Integral Trees, The Electronic Journal of Combinatorics, volume 15, 2008.
A. E. Brouwer, Integral Trees web page.
CROSSREFS
Sequence in context: A373202 A319330 A291204 * A111025 A271620 A374214
KEYWORD
nonn,more
AUTHOR
Kevin Ryde, Jan 16 2020
STATUS
approved