\documentclass[a4paper]{article}
\usepackage{latexsym}

\newtheorem{Theorem}{Theorem}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Corollary}[Theorem]{Corollary}
\newcommand{\qed}{\hfill$\Box$\medskip}
\newcommand{\adj}{\sim}
\newcommand{\tim}{$\times$}

\title{Small integral trees}
\author{A. E. Brouwer}
\date{2007-12-31}

\begin{document}
\maketitle

\abstract{We give a table with all integral trees on at most 50 vertices,
and characterize integral trees with a single eigenvalue 0.}

\section{Integral trees}
A finite graph is called {\em integral} if the spectrum of its
adjacency matrix has only integral eigenvalues.
A {\em tree} is a connected undirected graph without cycles.

In this note we give a table with all integral trees on at most 50 vertices,
and a further table with all known integral trees on at most 100 vertices.
(For an on-line version, possibly with updates, see \cite{aeb07}.)
In particular, we find the smallest integral trees of diameter 6,
and the smallest known integral tree of diameter 8.

The nicest result about integral trees is that by Watanabe \cite{Wat79}
that says that an integral tree different from $K_2$ does not have
a complete matching. Here we give a generalization.

All `starlike' integral trees, that is, all integral trees with
at most one vertex of degree larger than 2, were given by
Watanabe and Schwenk \cite{WS79}.

All integral trees of diameter at most 3 were given in \cite{WS79,Gra80}.
See also \cite{Schw80,Cao88}.

Several people have worked on constructing integral trees with
large diameter, and examples with diameters 0--8 and 10 are known,
% diameter 0-4: WS79
% diameter 5: Liu88
% diameter 6: Cao88
% diameter 7: HP07
% diameter 8: HN98
% diameter 10: HP03
see \cite{WS79,Liu88,Cao88,HP07,HN98,HP03}.
% see \cite{Cao88,Cao91,HN98,HP03,HP07,Li98,Liu88,WBHLS07,WL00,WL05,
% WLL99,WLY02,WLZ04}.
It is unknown whether integral trees can have arbitrarily large diameter.
% But see MR1884033 (2002k:05062)

The {\em spectral radius} of a nonempty graph is the maximum absolute value
of an eigenvalue. In \cite{BH} all integral trees with spectral radius
at most 3 are determined.

\subsection{Names of general trees}
In the tables below, we need a notation to name trees.
Given a tree, pick some vertex and call it the {\em root}.
Now walk along the tree (depth-first), starting at the root, and when
a vertex is encountered for the first time, write down its distance
to the root.
The sequence of integers obtained is called a {\em level sequence}
for the tree. A tree is uniquely determined by any level sequence.
The parent of a vertex labeled $m$ is the last vertex
encountered earlier that was labeled $m-1$.

For example, the graph $K_{1,4}$ gets level sequence 01111 if the
vertex of degree 4 is chosen as root, and 01222 otherwise.

We use exponents to indicate repetition: 01111 can be written $01^4$
and 0121212 as $0(12)^3$.

\begin{figure}
\begin{center}
\begin{picture}(160,120)(20,30)
\put(100,100){\circle*{4}}
\put(100,124){\circle*{4}}
\put(100,76){\circle*{4}}
\put(100,52){\circle*{4}}
\put(100,28){\circle*{4}}
\put(80,136){\circle*{4}}
\put(80,112){\circle*{4}}
\put(80,88){\circle*{4}}
\put(80,64){\circle*{4}}
\put(80,40){\circle*{4}}
\put(120,136){\circle*{4}}
\put(120,112){\circle*{4}}
\put(120,88){\circle*{4}}
\put(120,64){\circle*{4}}
\put(120,40){\circle*{4}}
\put(60,124){\circle*{4}}
\put(60,100){\circle*{4}}
\put(60,76){\circle*{4}}
\put(60,52){\circle*{4}}
\put(140,124){\circle*{4}}
\put(140,100){\circle*{4}}
\put(140,76){\circle*{4}}
\put(140,52){\circle*{4}}
\put(40,88){\circle*{4}}
\put(40,64){\circle*{4}}
\put(160,88){\circle*{4}}
\put(160,64){\circle*{4}}
\put(144,112){\circle*{4}}
\put(56,112){\circle*{4}}
\put(132,132){\circle*{4}}
\put(68,132){\circle*{4}}
\put(100,124){\line(0,-1){96}}
\put(60,124){\line(5,-3){100}}
\put(140,124){\line(-5,-3){100}}
\put(60,100){\line(5,-3){20}}
\put(60,100){\line(-5,-3){20}}
\put(140,100){\line(5,-3){20}}
\put(140,100){\line(-5,-3){20}}
\put(80,88){\line(0,-1){24}}
\put(120,88){\line(0,-1){24}}
\put(80,64){\line(-5,-3){20}}
\put(120,64){\line(5,-3){20}}
\put(100,52){\line(-5,-3){20}}
\put(100,52){\line(5,-3){20}}
\put(80,136){\line(0,-1){24}}
\put(120,136){\line(0,-1){24}}
\put(80,112){\line(-1,0){24}}
\put(120,112){\line(1,0){24}}
\put(80,112){\line(-3,5){12}}
\put(120,112){\line(3,5){12}}
\end{picture}
\end{center}
\caption{\#17: $0123^3(1(23)^3)^2(12^4)^21$.}
\end{figure}

\subsection{Names of special trees}
In the below we shall have use for some more or less standard
tree names. Some of the constructions below require a rooted
tree as input, and we indicate the root.

\medskip
A) $K_1$ is a single vertex. $K_2$ is a single edge.
(Any of the two vertices can serve as root.)

B) $K_{1,m}$ is the star on $m+1$ vertices. Its root is the central vertex.

C) If $G$ is a tree, then $SG$ is the subdivision of $G$
(with one new vertex in the middle of each edge of $G$).
If $G$ is rooted, then so is $SG$, with the same root.

D) If $G$ and $H$ are rooted trees, then $G \sim H$ is the tree
obtained from the disjoint union of $G$ and $H$ by joining the
roots. The resulting tree does not have a designated root.

E) Consider for rooted trees $G_1,...,G_s$ the rooted tree
$C(G_1,...,G_s)$ obtained by adding a new vertex to the disjoint
union of the $G_i$, joining the new vertex to the root of each $G_i$,
and taking this new vertex to be the root of $C(G_1,...,G_s)$.
For example, $C(mK_1)$ is $K_{1,m}$ and $C(mK_2)$ is $SK_{1,m}$.
(Here $mH$ denotes the disjoint union of $m$ copies of $H$.)

F) Define rooted trees $T(n_k,...,n_1)$ by induction on $k$ as follows:
$T()$ is $K_1$ and $T(n_k,...,n_1) = C(n_kT(n_{k-1},...,n_1))$ for $k > 0$.
For example, $T(m)$ is $K_{1,m}$, and $T(m,1)$ is $SK_{1,m}$.

G) If $G$ and $H$ are rooted trees, then $G * H$ is the rooted tree
obtained from the disjoint union of $G$ and $H$ by identifying the
roots. (The resulting vertex is the new root.)
For example, $T(s) * T(m,t)$ is $C(sK_1 + mK_{1,t})$.
(Here $G + H$ denotes the disjoint union of $G$ and $H$.)

Now tree \#17 depicted above is $T(1)*T(2,4)*T(1,1,3)*T(2,3,1)$.

\subsection{Families of integral trees}
We give some families of integral trees for later reference.
All except the last one occur in the literature.
Spectra are usually given with multiplicities written as exponents.

\medskip\noindent
{\it (i)} The spectrum of the complete bipartite graph $K_{1,m}$
(the tree $01^m$) is $\pm\sqrt{m}$, $0^{m-1}$.
It follows that $K_{1,m}$ is integral when
$m$ is a square (Harary \& Schwenk \cite{HS74}).

\medskip\noindent
{\it (ii)} The spectrum of $SK_{1,m}$ (the tree $0(12)^m$),
is $\pm\sqrt{m+1}$, $\pm 1^{m-1}$, $0$.
It follows that $SK_{1,m}$ is integral when $m+1$ is a square.

\medskip\noindent
Watanabe \& Schwenk \cite{WS79} showed that the graphs in (i) and (ii)
are the only integral trees with a single vertex of degree more than two.

\medskip\noindent
{\it (iii)} The spectrum of $K_{1,m} \sim K_{1,r}$ (the tree
$01^{m+1}2^r$), the result of joining the centers of $K_{1,m}$
and $K_{1,r}$, consists of $0^{m+r-2}$ together with the four roots
of $$X^4 - (m+r+1)X^2 + mr = 0.$$ These are integral for example when
$m = r = a(a+1)$ for some positive integer $a$ (and then the positive
roots are $a$ and $a+1$). There are also other solutions - the smallest
is $K_{1,50} \sim K_{1,98}$ on 150 vertices.
The question which $m$ and $r$ give integral solutions was settled
by Graham \cite{Gra80}.

\medskip\noindent
{\it (iv)} The spectrum of $K_{1,m} \sim SK_{1,r}$ (the tree
$01^{m+1}(23)^r$), the result of joining the centers of $K_{1,m}$
and $SK_{1,r}$, consists of $0^m$ and $\pm 1^{r-1}$ together with
the four roots of $$X^4 - (m+r+2)X^2 + mr+m+1.$$
These are integral for example for $m+1 = r = a(a+1)$
and for $m-1 = r+2 = a(a+1)$
(and in both cases the positive roots are $a$ and $a+1$).
There are also other solutions - the smallest is
$K_{1,287} \sim SK_{1,144}$ on 577 vertices.
One can find all solutions by the method of Graham \cite{Gra80}.

\medskip\noindent
Watanabe \& Schwenk \cite{WS79} also studied the situation with
two adjacent vertices of degree more than two, and proved that
in that situation one must have one of the examples given under
(iii) and (iv).

\medskip\noindent
{\it (v)} The spectrum of $T(r,m)$ is
$\pm \sqrt{r+m}$, $\pm \sqrt{m}^{r-1}$, $0^{mr-r+1}$.
Thus, this graph is integral precisely when both $m$ and $r+m$ are squares
(Watanabe \& Schwenk \cite{WS79}).

\medskip\noindent
Many other families have been studied, especially by Chinese mathematicians,
but most have not more than one or two representatives in the tables below,
and we refer directly to the literature. Remains to give a uniform explanation
for many of the remaining graphs.

\begin{Lemma} Consider the tree $T(a)*T(b,1)*T(c,4)*T(d,1,3)*T(e,3,1)$,
that is, $01^a(12)^b(12222)^c(12333)^d(1232323)^e$.
It is integral when it is
$01^a$ with $a = t^2$ (that is, $K_{1,a}$, case (i) above),
or $0(12)^b$ with $b = t^2 - 1$ (that is, $SK_{1,b}$, case (ii) above),
or $0(12222)^c$ with $c = t^2 - 4$ (that is, $T(c,4)$, part of case (v) above),
or when $b = 0$, $c = 3a+2d-3$, $e = t^2-4a-3d$.
In this last case the nonnegative eigenvalues are 0, 1, 2, $t$,
with multiplicities $10a+9d+e-10$, $2e+1$, $3a+3d+e-4$, $1$,
respectively. \qed
\end{Lemma}

For example, for $t=3$ and $(a,d)=(2,0)$, (1,1), (0,3), (1,0), (0,2),
this yields examples \#12, 17, 18, 22, 23.

\subsection{Tables}

The first table gives all integral trees on at most 50 vertices.
Here $n$ is the number of vertices and $d$ is the diameter.
Since trees are bipartite, the spectrum is symmetric around 0,
and it suffices to give the nonnegative half.
Multiplicities are written as exponents.
The references (i)-(v) refer to the families described above
and due to Harary \& Schwenk \cite{HS74} (for (i)) and
Watanabe \& Schwenk \cite{WS79} (for (ii)--(v)).
Graphs \#1--8 were already mentioned in \cite{HS74}.
The reference Wang refers to Wang \cite{Wthesis}.

\medskip\noindent\begin{table}\begin{tabular}{|l|l|l|l|l|l|}
\hline
\# & $n$ & $d$ & tree & spectrum & ref \\
\hline
1 & 1 & 0 & 0 & $0$ & (i) \\
2 & 2 & 1 & 01 & $1$ & (i) \\
3 & 5 & 2 & 01111 & $2$, $0^{3}$ & (i) \\
4 & 6 & 3 & 012211 & $2$, $1$, $0^{2}$ & (iii) \\
5 & 7 & 4 & 0121212 & $2$, $1^{2}$, $0$ & (ii) \\
6 & 10 & 2 & $01^9$ & $3$, $0^{8}$ & (i) \\
7 & 14 & 3 & $012^61^6$ & $3$, $2$, $0^{10}$ & (iii) \\
8 & 17 & 2 & $01^{16}$ & $4$, $0^{15}$ & (i) \\
9 & 17 & 4 & $0(12)^8$ & $3$, $1^{7}$, $0$ & (ii) \\
10 & 17 & 4 & $012^7(12)^4$ & $3$, $2$, $1^{3}$, $0^{7}$ & (iv) \\
11 & 19 & 4 & $012^5(12)^6$ & $3$, $2$, $1^{5}$, $0^{5}$ & (iv) \\
12 & 25 & 5 & $01(23333)^322(12)^3$ & $3$, $2^{3}$, $1^{3}$, $0^{11}$ &
    Wang, p.\,58 \\
13 & 26 & 2 & $01^{25}$ & $5$, $0^{24}$ & (i) \\
14 & 26 & 4 & $0(12222)^5$ & $3$, $2^{4}$, $0^{16}$ & (v) \\
15 & 26 & 3 & $012^{12}1^{12}$ & $4$, $3$, $0^{22}$ & (iii) \\
16 & 31 & 4 & $0(12)^{15}$ & $4$, $1^{14}$, $0$ & (ii) \\
17 & 31 & 6 & $0123^3(1232323)^2(12222)^21$ &
    $3$, $2^{4}$, $1^{5}$, $0^{11}$ & new \\
18 & 31 & 6 & $0(12333)^3(12222)^3$ & $3$, $2^{5}$, $1$, $0^{17}$ &
    Wang, p.\,68 \\
19 & 35 & 4 & $012^{13}(12)^{10}$ & $4$, $3$, $1^{9}$, $0^{13}$ & (iv) \\
20 & 37 & 2 & $01^{36}$ & $6$, $0^{35}$ & (i) \\
21 & 37 & 4 & $012^{11}(12)^{12}$ & $4$, $3$, $1^{11}$, $0^{11}$ & (iv) \\
22 & 37 & 6 & $0(1232323)^51$ & $3$, $2^{4}$, $1^{11}$, $0^{5}$ &
    Yao \cite{Yao01} \\
23 & 37 & 6 & $0(12333)^2(1232323)^312^4$ &
    $3$, $2^{5}$, $1^{7}$, $0^{11}$ & new \\
24 & 42 & 3 & $012^{20}1^{20}$ & $5$, $4$, $0^{38}$ & (iii) \\
25 & 46 & 4 & $012^{14}(12222)^6$ & $4$, $3$, $2^{5}$, $0^{32}$ &
    Yuan \cite{Yuan98} \\
26 & 49 & 4 & $0(12)^{24}$ & $5$, $1^{23}$, $0$ & (ii) \\
27 & 50 & 2 & $01^{49}$ & $7$, $0^{48}$ & (i) \\
28 & 50 & 4 & $0(12222)^91^4$ & $4$, $2^{8}$, $1$, $0^{30}$ &
    Watanabe \cite{Wat79} \\
\hline
\end{tabular}
\caption{The integral trees on at most 50 vertices.}
\end{table}

\medskip
The second table gives all further known integral trees on
at most 100 vertices.

\medskip\noindent\begin{table}\begin{tabular}{|l|l|l|l|l|l|}
\hline
$n$ & $d$ & tree & spectrum & ref \\
\hline
55 & 5 & $01(23^9)^32^7(12)^{8\mathstrut}$ & 
    $4$, $3^{3}$, $2$, $1^{7}$, $0^{31}$ & Wang, p.\,57 \\
56 & 6 & $0111(12222)^8123331232323$ & 
    $4$, $2^{9}$, $1^{3}$, $0^{30}$ & new \\
59 & 4 & $012^{21}(12)^{18}$ & $5$, $4$, $1^{17}$, $0^{21}$ & (iv) \\
61 & 4 & $012^{19}(12)^{20}$ & $5$, $4$, $1^{19}$, $0^{19}$ & (iv) \\
61 & 4 & $0(12222)^{12}$ & $4$, $2^{11}$, $0^{37}$ & (v) \\
62 & 3 & $012^{30}1^{30}$ & $6$, $5$, $0^{58}$ & (iii) \\
62 & 4 & $012^{10}(12222)^{10}$ & 
    $4$, $3$, $2^{9}$, $0^{40}$ & Yuan \cite{Yuan98} \\
62 & 6 & $0111(12222)^6(1232323)^4$ & 
    $4$, $2^{9}$, $1^{9}$, $0^{24}$ & Wang, p.\,76 \\
62 & 6 & $011(12222)^7(12333)^2(1232323)^2$ & 
    $4$, $2^{10}$, $1^{5}$, $0^{30}$ & new \\
62 & 6 & $01(12222)^8(12333)^4$ & 
    $4$, $2^{11}$, $1$, $0^{36}$ & Wang, p.\,77 \\
65 & 2 & $01^{64}$ & $8$, $0^{63}$ & (i) \\
68 & 6 & $011(12222)^5(12333)(1232323)^5$ & 
    $4$, $2^{10}$, $1^{11}$, $0^{24}$ & new \\
68 & 6 & $01(12222)^6(12333)^3(1232323)^3$ & 
    $4$, $2^{11}$, $1^{7}$, $0^{30}$ & new \\
68 & 6 & $0(12222)^7(12333)^5(1232323)$ & 
    $4$, $2^{12}$, $1^{3}$, $0^{36}$ & new \\
71 & 4 & $0(12)^{35}$ & $6$, $1^{34}$, $0$ & (ii) \\
71 & 4 & $0(12^9)^7$ & $4$, $3^{6}$, $0^{57}$ & (v) \\
71 & 6 & $01^6(12^9)^2(1(23)^8)^2123^8$ & 
    $4$, $3^{4}$, $2$, $1^{14}$, $0^{31}$ & new \\
74 & 6 & $011(12222)^3(1232323)^8$ & 
    $4$, $2^{10}$, $1^{17}$, $0^{18}$ & Wang, p.\,76 \\
74 & 6 & $01(12222)^4(12333)^2(1232323)^6$ & 
    $4$, $2^{11}$, $1^{13}$, $0^{24}$ & new \\
74 & 6 & $0(12222)^5(12333)^4(1232323)^4$ & 
    $4$, $2^{12}$, $1^{9}$, $0^{30}$ & new \\
78 & 4 & $01^{25}12^{18}12^{32}$ & 
    $6$, $5$, $4$, $0^{72}$ & Wang, p.\,44 \\ % 3.1.14
80 & 6 & $01(12222)^2(12333)(1232323)^9$ & 
    $4$, $2^{11}$, $1^{19}$, $0^{18}$ & new \\
80 & 6 & $0(12222)^3(12333)^3(1232323)^7$ & 
    $4$, $2^{12}$, $1^{15}$, $0^{24}$ & new \\
81 & 6 & $0(123^8)^2(12^9)^6$ & 
    $4$, $3^{7}$, $1$, $0^{63}$ & Wang, p.\,68 \\
82 & 2 & $01^{81}$ & $9$, $0^{80}$ & (i) \\
86 & 3 & $012^{42}1^{42}$ & $7$, $6$, $0^{82}$ & (iii) \\
86 & 6 & $01(2343434)^{12}$ & $4$, $2^{11}$, $1^{25}$, $0^{12}$ & 
    Yao \cite{Yao01} \\ % see Wang, Li & Zhang (2004)
86 & 6 & $012222(12333)^2(1232323)^{10}$ & 
    $4$, $2^{12}$, $1^{21}$, $0^{18}$ & new \\
87 & 6 & $01^62^9(1(23)^8)^3(123^8)^2$ & 
    $4$, $3^{5}$, $2$, $1^{21}$, $0^{31}$ & new \\
89 & 4 & $012^{31}(12)^{28}$ & 
    $6$, $5$, $1^{27}$, $0^{31}$ & (iv) \\
89 & 5 & $01^6(12222)^{15}1232323$ & 
    $5$, $2^{15}$, $1^{3}$, $0^{51}$ & Wang, p.\,57 \\ % Cor 4.1.4(3)
91 & 4 & $012^{29}(12)^{30}$ & 
    $6$, $5$, $1^{29}$, $0^{29}$ & (iv) \\
91 & 6 & $01^4(12^9)^31(23^4)^5(123^8)^3$ & 
    $4$, $3^{6}$, $2^{5}$, $0^{67}$ & new \\
94 & 4 & $012^{22}(12222)^{14}$ & 
    $5$, $4$, $2^{13}$, $0^{64}$ & Yuan \cite{Yuan98} \\
95 & 6 & $01^5(12222)^{14}(12333)(1232323)^2$ & 
    $5$, $2^{16}$, $1^{5}$, $0^{51}$ & new \\
95 & 6 & $01^4(12222)^{15}(12333)^3$ & 
    $5$, $2^{17}$, $1$, $0^{57}$ & Wang, p.\,77 \\
97 & 4 & $0(12)^{48}$ & $7$, $1^{47}$, $0$ & (ii) \\
98 & 8 & $0(12)^3(12^9)^4(122(34)^7)^3$ & 
    $4$, $3^{6}$, $2$, $1^{23}$, $0^{36}$ & new \\
\hline
\end{tabular}
\caption{Further integral trees on at most 100 vertices.}
\end{table}

\medskip

\section{Discussion}
Remains the question how one can compute a table of all integral
trees on at most 50 vertices. There are 10545233702911509534
nonisomorphic trees on 50 vertices, more than $10^{19}$, so testing
them one by one would not work.

Our approach is via interlacing. If $x$ is a vertex of a graph $G$,
and $G \setminus x$ the result of deleting $x$ from $G$, then the
eigenvalues of $G \setminus x$ interlace those of $G$.
It follows that if $G \setminus x$ has two eigenvalues strictly
between two successive integers $a$ and $a+1$, then $G$ has an
eigenvalue strictly between $a$ and $a+1$ and hence is not integral.

Now the spectrum of a disconnected graph is the union of the spectra
of the components, so one can conclude that $G \setminus x$ has two
eigenvalues strictly between $a$ and $a+1$ from the fact that this
is true for a component, or for the union of some of its components.
This is what we used: use a recursive procedure (depth first) that
constructs all trees. Each time for some vertex $x$ one or more components
of $G \setminus x$ have been completed, compute the spectrum of
the union of those components, and discard that branch of the computation
when two eigenvalues strictly between two successive integers are found.

\section{Integral trees with few eigenvalues 0}
\begin{Theorem} {\rm (Watanabe \cite{Wat79})}
An integral tree cannot have a complete matching, that is,
must have an eigenvalue $0$, unless it is $K_2$.
\end{Theorem}

\noindent{\bf Proof}\quad
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 $\pm 1$
and the tree is integral, then all eigenvalues are $\pm 1$
and the path of length 2 is not an induced subgraph,
so we have $K_2$. \qed

This argument can be extended a little.

\begin{Theorem}
If an integral tree has $0$ as eigenvalue with multiplicity $1$,
then the tree is $SK_{1,m}$ for some $m$.
\end{Theorem}

\noindent{\bf Proof}\quad
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 (up to a
nonzero constant) 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 a vertex $p$, and the graph $T \setminus 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 \setminus 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.

Let $t$ run over the positive eigenvalues of the adjacency matrix $A$ of $T$.
Considering the trace of $A^2$ (which equals twice the number of edges)
we see that $\sum t^2 = 2m$.
By the above we have $\prod t^2 \le m+1$.

Since $T$ is integral these $m$ eigenvalues $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}$.
\qed

{\bf 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$.


\begin{thebibliography}{999}

\bibitem{aeb07} A. E. Brouwer,\\
{\tt \verb#http://www.win.tue.nl/~aeb/graphs/integral_trees.html#}

% \bibitem{BCN} A. E. Brouwer, A. M. Cohen and A. Neumaier,
% {\it Distance-Regular Graphs}, Springer-Verlag, 1989.

\bibitem{BH} A. E. Brouwer and W. H. Haemers,
{\it The integral trees with spectral radius 3},
preprint, Sept. 2007.

\bibitem{Cao88} Z. F. Cao,
{\it Integral trees of diameter R $(3 \le R \le 6)$} (in Chinese),
Heilongjiang Daxue Ziran Kexue Xuebao {\bf 2} (1988) 1--3, 95.
% elsewhere: J. Heilongjiang University
% classifies the case of diameter 3

% Zhen Fu Cao
% \bibitem{Cao91} Z. F. Cao,
% {\it Some new classes of integral trees with diameter 5 or 6} (in Chinese),
% J. Systems Sci. Math. Sci. {\bf 11} (1991), no.1, 20--26.

\bibitem{Gra80} R. L. Graham,
{\it On a Diophantine Equation Arising in Graph Theory},
Europ. J. Comb. {\bf 1} (1980) 107--112.

\bibitem{HS74} F. Harary and A. J. Schwenk,
{\it Which graphs have integral spectra?},
In: Graphs and Combinatorics,
% (eds. R. Bari and F. Harary),
% (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973),
Lecture Notes in Mathematics 406, Springer-Verlag, Berlin (1974), 45--51.

% \bibitem{Hic97} P. H\'{\i}c,
% {\it On balanced integral trees of diameter 6}, CO-MAT-TECH ù97, 5.
% vedeck´a konferencia s medzin´arodnou ´u´cas´tou,
% Trnava 14--15 (1997), 125--129.

\bibitem{HN98} P. H\'{\i}c and R. Nedela,
{\it Balanced integral trees}, Math. Slovaca {\bf 48} (1998) 429--445.
% It is shown that there are infinitely many balanced integral trees
% of diameter 8, but there are none of diameter $4k+1$ for $k \ge 1$.

% Pavel H\'{\i}c and Milan Pokorn\'{y}
\bibitem{HP03} P. H\'{\i}c and M. Pokorn\'{y},
{\it On integral balanced rooted trees of diameter 10},
Acta Univ. M. Belii Math {\bf 10} (2003) 9--15.

\bibitem{HP07} P. H\'{\i}c and M. Pokorn\'{y},
{\it There are integral trees of diameter 7},
Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. {\bf 18} (2007) 59--63.

% Maosheng Li, Wensheng Yang, Jiabao Wang
% \bibitem{LYW00} M. S. Li, W. S. Yang and J. B. Wang,
% {\it Notes on the spectra of trees with small diameters} (in Chinese),
% J. Changsha Railway University 18 (2000) 84--87.

% \bibitem{LL87} X. L. Li and G. N. Lin,
% {\it On trees with integer eigenvalues},
% % or: On the problem of integral trees
% Kexue Tongbao (Chinese Ed.) {\bf 32} (1987), no.11, 813--816 (in Chinese),
% or {\it On integral trees problems},
% Kexue Tongbao (English Ed.) {\bf 33} (1988), no.10, 802--806 (in English).

% \bibitem{LW00} X. L. Li and L. G. Wang,
% {\it Integral trees---a survey} (in Chinese),
% Chinese Journal of Engineering Math. (or Gongcheng Shuxue Xuebao)
% {\bf 17} (2000), no.suppl., 91--93, 96.

% \bibitem{Li98} Y. Li,
% {\it A new class of integral trees with diameter 5} (in Chinese),
% J. Math. Res. Exposition {\bf 18} (1998), no.3, 435--438.

% Ru Ying Liu
\bibitem{Liu88} R. Y. Liu,
{\it Integral trees of diameter 5} (in Chinese),
J. Systems Sci. Math. Sci. {\bf 8} (1988), no.4, 357--360.
%  Let $T(m,r)$ be the graph obtained by connecting the centers
%  of the two star graphs $K_{1,m}$ and $K_{1,r}$,
%  and let $T^* (m,r,t)$ be the graph obtained by connecting
%  each vertex of $T(m,r)$ to $t$ new vertices.
%  The following theorems are proved: For each integral solution
%  $(b,s)\not=(1,1)$ of the Pell equation $x^2-2y^2=-1$,
%  and defining $m=2s^2$, $r=2b^2$, and $t =((b^2-1)/4)^2$,
%  $T^*(m,r,t)$ is an integral tree of diameter 5.
%  As a corollary there exist infinitely many integral trees of diameter 5.

% \bibitem{Liu88a} R. Y. Liu,
% {\it Some new families of trees with integral eigenvalues} (in Chinese),
% J. Qinghai Normal University {\bf 3} (1988) 1--5.

% \bibitem{R06} I. K. Redchuk,
% {\it Separating functions and spectra of starlike graphs},
% preprint, 2006.

% \bibitem{Ren00} Haizhen Ren,
% {\it On integral trees with diameter four},
% J. Qinghai Normal Univ. {\bf 1} (2000) 8--11.

\bibitem{Schw80} A. J. Schwenk,
{\it Trees with integral eigenvalues},
Problem 23 in: {\it A collection of open problems},
M.~Capobianco, S.~Maurer, D.~McCarthy and J.~Molluzzo (eds.),
pp. 565--590 in: Proc. Second International Conference on
Combinatorial Mathematics (A.~Gewirtz and L.~V.~Quintas, Eds.),
Ann. New York Acad. Sci. {\bf 319} (1980) 582--583.

\bibitem{Wthesis} Ligong Wang,
{\it Integral graphs and integral trees},
Ph. D. thesis, Univ. Twente, 2005.

% Ligong Wang, Hajo Broersma, Cornelis Hoede, Xueliang Li, Georg Still
% \bibitem{WBHLS07} L. G. Wang, H. J. Broersma, C. Hoede, X. L. Li
% and G. Still,
% {\it Integral trees of diameter 6},
% Discrete Applied Mathematics 155 (2007) 1254--1266.
% In this paper, the trees T(p,q)*T(r,m,t) and K''1'',''s*T(p,q)*T(r,m,t)
% of diameter 6 are defined.

% \bibitem{WL00} L. G. Wang and X. L. Li,
% {\it Some new classes of integral trees with diameters 4 and 6},
% Australas. J. Combin. 21 (2000), 237--243.

% Ligong Wang, Xueliang Li
% \bibitem{WL05} L. G. Wang and X. L. Li,
% {\it Integral trees with diameters 5 and 6},
% Discrete Math. {\bf 297} (2005) 128--143.

% \bibitem{WLL99} L. G. Wang, X. L. Li and R. Y. Liu,
% {\it Integral trees with diameter 6 or 8},
% 6th Twente Workshop on Graphs and Combinatorial Optimization
% (Enschede, 1999), 6 pp. (electronic),
% Electron. Notes Discrete Math. 3, Elsevier, Amsterdam (1999).

% \bibitem{WLY02} L. G. Wang, X. L. Li and X. J. Yao,
% {\it Integral trees with diameters 4, 6 and 8},
% Australas. J. Combin. {\bf 25} (2002), 29--44.

% Ligong Wang, Xueliang Li, Shenggui Zhang
% \bibitem{WLZ04} L. G. Wang, X. L. Li and S. G. Zhang,
% {\it Families of integral trees with diameters 4, 6 and 8},
% Discrete Appl. Math. {\bf 136} (2004) 349--362.
% (or L.G. Wang, X.L. Li and S.G. Zhang,
% Some new families of integral trees with diameters 4 and 6,
% Electronic Notes in Discrete Math. vol. 8 (2001)).

\bibitem{Wat79} M. Watanabe,
{\it Note on integral trees},
Math. Rep. Toyama Univ. 2 (1979), 95--100.

\bibitem{WS79} M. Watanabe and A. J. Schwenk,
{\it Integral starlike trees},
J. Austral. Math. Soc. (A) {\bf 28} (1979) 120--128.

% Dashen Xu
% \bibitem{Xu96} D. S. Xu,
% {\it A note on the integral trees with diameter 4} (in Chinese),
% J. Qinghai University 14 (1996) 16--18.

% \bibitem{Xu97} D. S. Xu,
% {\it Some new classes of the integral trees with diameter 4} (in Chinese),
% J. Hebei University 17 (1997) 12--16.

% Xiangyuan Yao,
\bibitem{Yao01} X. Y. Yao,
{\it Integral trees and integral digraphs} (in Chinese),
MSc. Thesis, Northwestern Polytechnical University, China, 2001.

% Pingzhi Yuan
\bibitem{Yuan98} P. Z. Yuan,
{\it Integral trees of diameter 4} (in Chinese),
J. Systems Sci. Math. Sci. 18 (1998), no.2, 177--181.

% \bibitem{ZT00} D. L. Zhang and S. W. Tan,
% {\it Integral trees of diameter 4} (in Chinese),
% J. Systems Sci. Math. Sci. 20 (2000) 330--337.

% De-long Zhang and Lan-yong Wei
% \bibitem{ZW98} D. L. Zhang and L. Y. Wei,
% {\it On the existence of integral trees of diameter 4} (in Chinese),
% J. Guangxi Institute of Technology 9 (1998) 1--5.

\end{thebibliography}

\end{document}

APPLIED MATHEMATICS A JOURNAL OF CHINESE UNIVERSITIES
http://www.math.zju.edu.cn/amjcu/B/200003/mle.htm
http://www.math.zju.edu.cn/amjcu/zclE.asp
