

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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, SpringerVerlag, Berlin, 1974.


LINKS

Table of n, a(n) for n=0..50.
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: A175562 A319330 A291204 * A111025 A271620 A098018
Adjacent sequences: A331411 A331412 A331413 * A331415 A331416 A331417


KEYWORD

nonn,more


AUTHOR

Kevin Ryde, Jan 16 2020


STATUS

approved



