There are 0, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320, 48629, 123867, 317955, 823065, 2144505, 5623756, 14828074, 39299897, 104636890, 279793450, 751065460, 2023443032, 5469566585, 14830871802, 40330829030, 109972410221, 300628862480, 823779631721, 2262366343746, 6226306037178, 17169677490714, 47436313524262, 131290543779126, 363990257783343 trees on 0–40 vertices, respectively. This is Sequence A000055 in Sloane's On-Line Encyclopedia of Integer Sequences. (Except that he starts with 1, but there are no trees on 0 vertices: just like 1 is not a prime number but a product of zero primes, the empty graph is not connected, but a forest with zero trees.)

Only very few of all these trees have only integral eigenvalues.
Examples are known of diameters 0–8 and 10. It ~~ is ~~ was unknown
whether integral trees of arbitrary diameter exist.
(Péter Csikvári (2010) has constructed integral trees
with arbitrary even diameter, see below.
Ebrahim Ghorbani et al. (2011) settled the odd-diameter case.)

There are many papers on integral trees, but I have not seen tables with a complete enumeration of all small integral trees. Here a table with all on at most 50 vertices.

Since the spectrum is symmetric around 0, it suffices to give the nonnegative half. Multiplicities are written as exponents.

The tree is given by a level sequence.

# | n | d | name | tree | spectrum |

1 | 1 | 0 | K_{1} | 0 | 0 |

2 | 2 | 1 | K_{2} | 01 | 1 |

3 | 5 | 2 | K_{1,4} | 01111 | 2,0^{3} |

4 | 6 | 3 | K_{1,2}~K_{1,2} |
012211 | 2,1,0^{2} |

5 | 7 | 4 | SK_{1,3} |
0121212 | 2,1^{2},0 |

6 | 10 | 2 | K_{1,9} |
0111111111 | 3,0^{8} |

7 | 14 | 3 | K_{1,6}~K_{1,6} |
01222222111111 | 3,2,0^{10} |

8 | 17 | 2 | K_{1,16} |
01111111111111111 | 4,0^{15} |

9 | 17 | 4 | SK_{1,8} |
01212121212121212 | 3,1^{7},0 |

10 | 17 | 4 | K_{1,7}~SK_{1,4} |
01222222212121212 | 3,2,1^{3},0^{7} |

11 | 19 | 4 | K_{1,5}~SK_{1,6} |
0122222121212121212 | 3,2,1^{5},0^{5} |

12 | 25 | 5 | T(2)*T(3,4)~T(3,1) | 0123333233332333322121212 | 3,2^{3},1^{3},0^{11} |

13 | 26 | 2 | K_{1,25} |
01111111111111111111111111 | 5,0^{24} |

14 | 26 | 4 | T(5,4) | 01222212222122221222212222 | 3,2^{4},0^{16} |

15 | 26 | 3 | K_{1,12}~K_{1,12} |
01222222222222111111111111 | 4,3,0^{22} |

16 | 31 | 4 | SK_{1,15} |
0121212121212121212121212121212 | 4,1^{14},0 |

17 | 31 | 6 | T(1)*T(2,4)*T(1,1,3)*T(2,3,1) | 0123331232323123232312222122221 | 3,2^{4},1^{5},0^{11} |

18 | 31 | 6 | T(3,4)*T(3,1,3) | 0123331233312333122221222212222 | 3,2^{5},1,0^{17} |

19 | 35 | 4 | K_{1,13}~SK_{1,10} |
01222222222222212121212121212121212 | 4,3,1^{9},0^{13} |

20 | 37 | 2 | K_{1,36} |
0111111111111111111111111111111111111 | 6,0^{35} |

21 | 37 | 4 | K_{1,11}~SK_{1,12} |
0122222222222121212121212121212121212 | 4,3,1^{11},0^{11} |

22 | 37 | 6 | T(1,5,3,1) | 0123232312323231232323123232312323231 | 3,2^{4},1^{11},0^{5} |

23 | 37 | 6 | T(1,4)*T(2,1,3)*T(3,3,1) | 0123331233312323231232323123232312222 | 3,2^{5},1^{7},0^{11} |

24 | 42 | 3 | K_{1,20}~K_{1,20} |
01^{20}12^{20} | 5,4,0^{38} |

25 | 46 | 4 | T(6,4)*T(1,14) | 012^{14}(12222)^6 | 4,3,2^{5},0^{32} |

26 | 49 | 4 | SK_{1,24} |
0(12)^{24} | 5,1^{23},0 |

27 | 50 | 2 | K_{1,49} |
01^{49} | 7,0^{48} |

28 | 50 | 4 | T(4)*T(9,4) | 0(12222)^91^4 | 4,2^{8},1,0^{30} |

Symbols used in the graph name:

K_{m} is the complete graph on m vertices.

K_{1,m} is the star on m+1 vertices. (It has an obvious center.)

SX is the subdivision of X. (It has the same center as X, if any.)

G~H is the result of joining the center of G with the center of H by an edge. (Here `center' is defined by induction. The result does not have a center.)

C(G_{1},...) is the cone over G_{1},..., that is,
the result of joining a new vertex to the center of each of the G_{i}.
(The new vertex is the center.)
For example, K_{1,m} is C(mK_{1}), and
SK_{1,m} is C(mK_{2}).

T(n_{k},...,n_{1}) is defined by induction on k as
the graph C(n_{k}T(n_{k-1},...,n_{1})),
where T() is a single vertex. For example, K_{1,m} is T(m),
and SK_{1,m} is T(m,1).

G*H is the graph obtained from the disjoint union of G and H
by identifying the centers of G and H.
For example, C(mK_{1,t}+sK_{1}) is T(s)*T(m,t).

√m, 0It follows that K^{m–1}, –√m.

√(m+1), 1It follows that SK^{m–1}, 0, (–1)^{m–1}, –√(m+1).

Watanabe & Schwenk (1979) showed that these graphs are the only integral trees with a single vertex of degree more than two.

They also studied the situation with two adjacent vertices
of degree more than two, and proved that in that situation one has
either K_{1,m}~K_{1,r} or
K_{1,m}~SK_{1,r}.
(They were unable to handle the case of two nonadjacent vertices
of degree more than two, but using interlacing and Godsil's Lemma
it is not difficult to see that that does not yield any further examples -
see Brouwer (2009).)

xhas only integral roots. (The spectrum consists of 0^{4}– (m+r+1)x^{2}+ mr

xhas only integral roots. (The spectrum consists of (–1)^{4}– (m+r+2)x^{2}+ mr + m + 1

xhas only integral roots, and t is a square, and either q=1 or r is a square. (The positive spectrum consists of 0 with multiplicity m(t–1)+q(r–1)+s, and √t with multiplicity m, and √r with multiplicity q–1, and the two positive roots of the above polynomial.)^{4}– (m+t+s+1)x^{2}+ st + r

The graph T(2)*T(3,4)~T(3,1) on 25 vertices was given by Wang (2005), p. 58. This is #12. It is the smallest integral tree of diameter 5.

The next smallest case is T(7)*T(3,9)~T(8,1) on 55 vertices.

The graph T(3,4)*T(3,1,3) on 31 vertices was given by Ligong Wang (2005), p. 68. This is #18.

Graphs #17, 18 are the smallest integral trees of diameter 6.

The graph T(1,5,3,1) on 37 vertices is due to Yao (2001) (cf. Wang (2005), p. 47). This is #22.

Graph #23 is perhaps given here for the first time. It is T(1,4)*T(2,1,3)*T(3,3,1).

The graph T(6,4)*T(1,14) on 46 vertices may be due to Yuan (1998). This is #25.

The graph T(4)*T(9,4) on 50 vertices was given by Watanabe (1979). This is #28.

n | d | name | tree | spectrum | reference |

55 | 5 | T(7)*T(3,9)~T(8,1) | 01(23^9)^32^7(12)^8 | 4,3^{3},2,1^{7},0^{31} |
Wang (2005), p. 57 |

56 | 6 | T(3)*T(8,4)*T(1,1,3)*T(1,3,1) | 0111(12222)^8123331232323 | 4,2^{9},1^{3},0^{30} |
new |

59 | 4 | K_{1,21}~SK_{1,18} |
012^{21}(12)^{18} | 5,4,1^{17},0^{21} |
WS |

61 | 4 | K_{1,19}~SK_{1,20} |
012^{19}(12)^{20} | 5,4,1^{19},0^{19} |
WS |

61 | 4 | T(12,4) | 0(12222)^{12} | 4,2^{11},0^{37} |
WS |

62 | 3 | K_{1,30}~K_{1,30} |
012^{30}1^{30} | 6,5,0^{58} |
WS |

62 | 4 | T(10,4)*T(1,10) | 012^{10}(12222)^{10} | 4,3,2^{9},0^{40} |
Yuan (1998)? |

62 | 6 | T(3)*T(6,4)*T(4,3,1) | 0111(12222)^6(1232323)^4 | 4,2^{9},1^{9},0^{24} |
Wang (2005), p. 76 |

62 | 6 | T(2)*T(7,4)*T(2,1,3)*T(2,3,1) | 011(12222)^7(12333)^2(1232323)^2 | 4,2^{10},1^{5},0^{30} |
new |

62 | 6 | T(1)*T(8,4)*T(4,1,3) | 01(12222)^8(12333)^4 | 4,2^{11},1,0^{36} |
Wang (2005), p. 77 |

65 | 2 | K_{1,64} |
01^{64} | 8,0^{63} |
WS |

68 | 6 | T(2)*T(5,4)*T(1,1,3)*T(5,3,1) | 011(12222)^5(12333)(1232323)^5 | 4,2^{10},1^{11},0^{24} |
new |

68 | 6 | T(1)*T(6,4)*T(3,1,3)*T(3,3,1) | 01(12222)^6(12333)^3(1232323)^3 | 4,2^{11},1^{7},0^{30} |
new |

68 | 6 | T(7,4)*T(5,1,3)*T(1,3,1) | 0(12222)^7(12333)^5(1232323) | 4,2^{12},1^{3},0^{36} |
new |

71 | 4 | SK_{1,35} |
0(12)^{35} | 6,1^{34},0 |
WS |

71 | 4 | T(7,9) | 0(12^9)^7 | 4,3^{6},0^{57} |
WS |

71 | 6 | T(6)*T(2,9)*T(2,8,1)*T(1,1,8) | 01^6(12^9)^2(1(23)^8)^2123^8 | 4,3^{4},2,1^{14},0^{31} |
new |

74 | 6 | T(2)*T(3,4)*T(8,3,1) | 011(12222)^3(1232323)^8 | 4,2^{10},1^{17},0^{18} |
Wang (2005), p. 76 |

74 | 6 | T(1)*T(4,4)*T(2,1,3)*T(6,3,1) | 01(12222)^4(12333)^2(1232323)^6 | 4,2^{11},1^{13},0^{24} |
new |

74 | 6 | T(5,4)*T(4,1,3)*T(4,3,1) | 0(12222)^5(12333)^4(1232323)^4 | 4,2^{12},1^{9},0^{30} |
new |

78 | 4 | K_{1,18}~K_{1,25}~K_{1,32} |
01^{25}12^{18}12^{32} | 6,5,4,0^{72} |
Wang (2005), 3.1.14 |

80 | 6 | T(1)*T(2,4)*T(1,1,3)*T(9,3,1) | 01(12222)^2(12333)(1232323)^9 | 4,2^{11},1^{19},0^{18} |
new |

80 | 6 | T(3,4)*T(3,1,3)*T(7,3,1) | 0(12222)^3(12333)^3(1232323)^7 | 4,2^{12},1^{15},0^{24} |
new |

81 | 6 | T(6,9)*T(2,1,8) | 0(123^8)^2(12^9)^6 | 4,3^{7},1,0^{63} |
Wang (2005), p. 68 |

82 | 2 | K_{1,81} |
01^{81} | 9,0^{80} |
WS |

86 | 3 | K_{1,42}~K_{1,42} |
012^{42}1^{42} | 7,6,0^{82} |
WS |

86 | 6 | T(1,12,3,1) | 01(2343434)^{12} | 4,2^{11},1^{25},0^{12} |
Yao (2001)? |

86 | 6 | T(1,4)*T(2,1,3)*T(10,3,1) | 012222(12333)^2(1232323)^{10} | 4,2^{12},1^{21},0^{18} |
new |

87 | 6 | T(5)*T(1,9)*T(3,8,1)*T(2,1,8) | 01^512^9(1(23)^8)^3(123^8)^2 | 4,3^{5},2,1^{21},0^{31} |
new |

89 | 4 | K_{1,31}~SK_{1,28} |
012^{31}(12)^{28} | 6,5,1^{27},0^{31} |
WS |

89 | 5 | T(6)*T(15,4)*T(1,3,1) | 01^6(12222)^{15}1232323 | 5,2^{15},1^{3},0^{51} |
Wang (2005), Cor 4.1.4(3) |

91 | 4 | K_{1,29}~SK_{1,30} |
012^{29}(12)^{30} | 6,5,1^{29},0^{29} |
WS |

91 | 6 | T(4)*T(3,9)*T(1,5,4)*T(3,1,8) | 01^4(12^9)^31(23^4)^5(123^8)^3 | 4,3^{6},2^{5},0^{67} |
new |

94 | 4 | T(14,4)*T(1,22) | 012^{22}(12222)^{14} | 5,4,2^{13},0^{64} |
Yuan (1998)? |

95 | 6 | T(5)*T(14,4)*T(1,1,3)*T(2,3,1) | 01^5(12222)^{14}(12333)(1232323)^2 | 5,2^{16},1^{5},0^{51} |
new |

95 | 6 | T(4)*T(15,4)*T(3,1,3) | 01^4(12222)^{15}(12333)^3 | 5,2^{17},1,0^{57} |
Wang (2005), p. 77 |

97 | 4 | SK_{1,48} |
0(12)^{48} | 7,1^{47},0 |
WS |

98 | 8 | T(3,1)*T(4,9)*C(3C(K_{1}+T(7,1))) |
0(12)^3(12^9)^4(122(34)^7)^3 | 4,3^{6},2,1^{23},0^{36} |
new |

The above example on 98 vertices is the smallest integral tree known of diameter 8.

Some version of the above two tables was published in Brouwer (2008).

Let K_{1,m1}~K_{1,m2}~
... ~K_{1,mt} denote a path with t vertices
and m_{i} pending edges at the i-th vertex.
Aart Blokhuis remarks that for t=3 and eigenvalues a–1,a,a+1
one gets Pell's equation u^{2}–2v^{2} = –1
with smallest solutions (m_{1},m_{2},m_{3}) =
(18,25,32) and (800,841,882).

It follows that if G is a tree with designated vertex x, and H a tree
with designated vertex y, and a tree T = G~mH is constructed
by taking G and m copies of H, where x is joined to the m copies of y, then
φ_{T} = φ_{H}^{m–1}(φ_{G}φ_{H}
– mφ_{G\x}φ_{H\y}).
By symmetry, if T is integral, and G is integral, then also the result
H~mG of taking H and attaching m copies of G is integral.

For example, suppose that T(p,q,r,...) is integral, where p > 1.
Then also H = T(q,r,...) is integral and we can apply this with
G = K_{1} to conclude that C(pK_{1}+qT(r,...))
is integral (and much smaller).
(For example, the integrality of T(4,9,4) of diameter 6 on 185 vertices
is equivalent to that of Watanabe's graph C(9K_{1,4}+4K_{1})
of diameter 4 on 50 vertices. And the integrality of T(5,4) of diameter 4
on 26 vertices is equivalent to that of K_{1,9} of diameter 2
on 10 vertices.)

This also immediately gives the integrality of Csikvári's trees (see below).

∑ t^{2}= n–1,

∑ t^{4}= ∑ d_{x}^{2}– (n–1),

∑ twhere d^{6}= ∑ d_{x}^{3}– 3 ∑ d_{x}^{2}+ 2(n–1) + 3 ∑ d_{x}d_{y}

**Proof**
Suppose T is a tree with a complete matching.
Then that matching is unique, since the union of two distinct
complete matchings contains a cycle.
Now the constant term of the characteristic polynomial is,
up to sign, the number of complete matchings. It is also the
product of all eigenvalues. If this constant term is 1 or –1
and the tree is integral, then all eigenvalues are 1 or –1
and the path of length 2 is not an induced subgraph,
so we have K_{2}. ∎

This argument can be extended a little.

**Theorem** (AEB)
*If an integral tree has* 0 *as eigenvalue with multiplicity* 1,
*then the tree is* SK_{1,m}.

**Proof**
Suppose T is a tree on n vertices with eigenvalue 0 of multiplicity 1.
Then it has almost matchings: coverings by m pairwise disjoint edges
and a single point, where n = 2m+1.
The number of such almost matchings is, up to sign, the product of the
nonzero eigenvalues. On the other hand, the number of such almost matchings
is precisely the number of nonzero entries of the unique eigenvector u for 0.
(If we delete a vertex where u is zero, then the resulting graph has
eigenvalue 0 and hence no matchings. Suppose that u is nonzero at p,
and the graph T\p has no matching. Then it has eigenvalue 0, and since
n–1=2m is even, this eigenvalue has multiplicity at least 2, so there
is an eigenvector v of T\p for 0 that sums to 0 on the neighbours of p.
But then v extended by a 0 on p is another eigenvector for 0 of T,
contradiction.)
This number of nonzero entries is at most (n+1)/2 = m+1, since the
nonzero entries form a coclique, and no vertex with zero entry
is adjacent to more than two vertices with nonzero entries.

This shows that ∑ t^{2} = 2m (from the trace of A^{2})
and ∏ t^{2} ≤ m+1 (from the above), where sum and product
are over the positive eigenvalues t. Since T is integral these t
are all at least 1, and the extremal situation is when all except one
are 1 and the last one has t^{2} = m+1. Since equality holds
we must be in this extremal situation and know the spectrum, it is
that of SK_{1,m}.

Now A^{2}–I has rank 3 (eigenvalue m with multiplicity 2
and –1 with multiplicity 1) and hence has rank 1 on one bipartite
half of T. The Perron-Frobenius eigenvector is positive everywhere,
so yields an eigenvector of A^{2}–I for both components,
with eigenvalue m. The vector u vanishes on one bipartite half.
That bipartite half is connected for steps of size 2, and has a rank 1
matrix, so has diameter 2, where each vertex has a unique path of
length 2 to every other vertex, and has degree 2 itself.
This forces the structure, and T must be SK_{1,m}.
∎

**Remark** The trees SK_{1,m} are determined by
their spectrum as trees, not as graphs. For example,
SK_{1,3} is cospectral with C_{6}+K_{1}.

**Remark** Ghorbani et al. (2016) show that only finitely many
integral trees have a given nullity larger than 1.
The unique integral tree with nullity 2 is K_{1,2}~K_{1,2}.
The unique integral tree with nullity 3 is K_{1,4.
}

**Theorem** (AEB & WHH)
*There are 11 integral trees with largest eigenvalue 3
(on 10, 14, 17, 17, 19, 25, 26, 31, 31, 37, 37 vertices, respectively).*
These trees have already been described above.

Apply this argument to the characteristic equations of
K_{1,m}~K_{1,r} and K_{1,m}~SK_{1,r}
The unknown eigenvalues a, –a, b, –b satisfy
a^{2}+b^{2} = m+r+1 and
a^{2}b^{2} = mr in the first case, and
a^{2}+b^{2} = m+r+2 and
a^{2}b^{2} = mr + m + 1 in the second case.

With A = b–a and B = b+a these are equivalent to
m,r = (A^{2}+B^{2}–2±2C)/4 where
C^{2} = (A^{2}–1)(B^{2}–1) in the first case,
and to m–1,r = (A^{2}+B^{2}–6±2C)/4 where
C^{2}–4 = (A^{2}–1)(B^{2}–1) in the second case.

By Graham descent we arrive after a number of steps at a solution with A ≤ 1. Now A = 0 does not give solutions with positive m,r, and A = 1 leads to B = 2a+1 and C = 0 and m,r = a(a+1) in the first case, and to B = 2a+1 and C = 2 and {m–1,r} = {a(a+1),a(a+1)–2}, that is, (m,r) = (a(a+1)+1,a(a+1)–2) or (a(a+1)–1,a(a+1)) in the second case.

For the first case Graham (1980) gives an explicit expression of A,B,C in terms of Chebyshev polynomials.

Integrality of these trees can also be seen using the above remark on characteristic polynomials. It implies that if T'(a+b,c,d,...) and T'(b,c,d,...) and T'(c,d,...) are integral, then also T'(a,b,c,d,...) is.

The trees T'(r,m) are the same as T(r,m). The trees T'(5,3,1) and T'(12,3,1) are the same as the trees T(1,5,3,1) and T(1,12,3,1) seen above. More generally, the trees T'(r,m,t) are the same as the trees T(t)*T(r,m,t) studied by Wang & Li (2000).

This yields integral trees of arbitrary even diameter. For example, an integral tree of diameter 12 on 27007 vertices. The case of large odd diameter was settled by Ghorbani et al. (2010) using a variation on this construction.

A. E. Brouwer & W. H. Haemers,
*The integral trees with spectral radius 3*,
Lin. Alg. Appl. **429** (2008) 2710–2718.
pdf

A. E. Brouwer,
*Integral trees homeomorphic to a double star*,
preprint, Sept. 2009.
pdf

Péter Csikvári,
*Integral trees of arbitrarily large diameters*,
J. Algebr. Combin. **32** (2010) 371-377.

E. Ghorbani, A. Mohammadian & B. Tayfeh-Rezaie,
*Integral trees of odd diameters*,
J. Graph Th. **70** (2011) 332-338.

E. Ghorbani, A. Mohammadian & B. Tayfeh-Rezaie,
*Integral trees with given nullity*,
Discrete Math. **339** (2016) 157-164.

R. L. Graham,
*On a Diophantine Equation Arising in Graph Theory*,
Europ. J. Comb. **1** (1980) 107–112.
pdf

F. Harary & A. J. Schwenk,
*Which graphs have integral spectra?*
pp. 45–51 in: Graphs and Combinatorics,
Lecture Notes in Mathematics 406, Springer-Verlag, Berlin, 1974.

Pavel Híc & Roman Nedela,
*Balanced integral trees*,
Math. Slovaca **48** (1998), no.5, 429–445.

Pavel Híc & Milan Pokorný, *On integral balanced rooted trees
of diameter 10*, Acta Univ. M. Belii Math no. 10 (2003) 9–15.
pdf

Pavel Híc & Milan Pokorný, *There are integral trees of diameter 7*,
Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. **18** (2006) 59–63.
pdf

Ligong Wang, *Integral Trees and Integral Graphs*,
Ph.D. Thesis, Univ. of Twente, 2005.
pdf

Ligong Wang & Xueliang Li,
*Some new classes of integral trees with diameters 4 and 6*,
Australasian J. Comb. **21** (2000) 237–243.
pdf

Ligong Wang, Xueliang Li & Shenggui Zhang,
*Families of integral trees with diameters 4, 6, and 8*,
Discrete Applied Mathematics **136** (2004) 349–362.
pdf

Mamoru Watanabe, *Note on integral trees*,
Math. Rep. Toyama Univ. **2** (1979) 95–100.

Mamoru Watanabe & Allen J. Schwenk,
*Integral starlike trees*,
J. Austral. Math. Soc. (A) **28** (1979) 120–128.

Xiangyuan Yao,
*Integral trees and integral digraphs* (Chinese),
MSc. Thesis, Northwestern Polytechnical University, China, 2001.

Pingzhi Yuan,
*Integral trees of diameter 4* (Chinese),
J. Systems Sci. Math. Sci. **18** (1998) 177–181.

Send corrections and additions to aeb@cwi.nl