\documentstyle[a4,12pt]{article}
\title{Determination of the distance-regular graphs without 3-claws}
\author{A. Blokhuis \& A.E. Brouwer \\
Dept. of Math., Eindhoven Univ. of Technology, \\
P.O. Box 513, Eindhoven, Netherlands}
\begin{document}
\section{}
\maketitle
\newtheorem{Theorem} {Theorem} [section]
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}
\newcommand{\eps}{\varepsilon}

\begin{abstract}
We determine the distance-regular graphs without induced $K_{1,3}$
subgraphs. There are no surprises.
\end{abstract}

\begin{Theorem}
Let $\Gamma$ be a strongly regular graph without induced $K_{1,3}$.
Then $\Gamma$ is one of:

\noindent
(i) The complement of a strongly regular graph without triangles.

\noindent
(ii) The Schl\"afli graph (with parameters $(v,k,\lambda,\mu)=(27,16,10,8)$).

\noindent
(iii) A triangular graph $T(n)$ (also known as ${n \choose 2}$).

\noindent
(iv) A lattice graph $L_2(n)$ (also known as $n \times n$).
\end{Theorem}

\Proof

Let $\Gamma$ have parameters $(v,k,\lambda,\mu)$ and eigenvalues $k,r,s$,
with multiplicities $1,f,g$, respectively, where $s < 0$. Then
$$s = {\lambda - \mu - \sqrt{(\lambda - \mu)^2 - 4(\mu - k)} \over 2} .$$
Suppose first that $s \le -3$. If $\lambda - \mu + 6 \ge 0$, it follows that
$(\lambda - \mu)^2 + 4(k - \mu) \ge (\lambda - \mu + 6)^2$. We conclude that

\noindent
(1) {\it If $s \le -3$, then $k + 2\mu \ge 3\lambda + 9$.}

If $\Gamma$ has a maximal coclique $C$ of size $c$, then each vertex not
in $C$ has either 1 or 2 neighbours in $C$, so that

\noindent
(2) $v = c + \mu {c \choose 2} + c\left(k - (c-1)\mu\right) = c(k+1) - \mu {c \choose 2}$,

\noindent
and $k \ge (c-1)\mu$. Put $k = (1+\eps)(c-1)\mu$, with $\eps \ge 0$, then (1)
yields $$3(k-\lambda-1) \ge 2k-2\mu+6$$ and (2) yields
$$(c-1)(k+1) - \mu{c \choose 2} = v-k-1 = {k \over \mu}(k - \lambda - 1) \ge
{1 \over 3}(1+\eps)(c-1)(2k-2\mu+6) ,$$
i.e.,
$$3(k+1) - {3 \over 2}\mu c \ge (1+\eps)(2k-2\mu+6) ,$$
i.e.,
$$(1-2\eps)k + (2\eps + 2 - {3 \over 2}c)\mu \ge 3 + 6\eps > 0, $$
so
$$(1-2\eps)(1+\eps)(c-1) + 2\eps + 2 - {3 \over 2}c > 0,$$
i.e.,
$$2\eps^2(c-1) + \eps(c-3) + {1 \over 2}c - 1 < 0,$$
contradiction for $c \ge 3$.
So, if we are not in case (i), we have $s > -3$.

But the eigenvalues of strongly regular graphs are integral, except possibly
in the case where $(v,k,\lambda,\mu) = (4t+1,2t,t-1,t)$ for some integer $t$.
Thus, in this case $k \ge (c-1)\mu$ implies $c = 3$ and $k = (c-1)\mu$.
On the other hand, if $k = (c-1)\mu$, then $\lambda = {1 \over 2} c\mu - 2$
and $r = {1 \over 2}(c-2)\mu$ and $s = -2$.

Thus, it suffices to look at the strongly regular graphs with smallest eigenvalue
$-2$. But these have been classified by Seidel \cite{S}. We find the examples
(ii)-(iv), and also the Petersen graph (which is locally a 3-coclique), and
the Shrikhande graph (which is locally a hexagon), and the Clebsch graph
and the complements of ladder graphs (which fall under case (i)), and the
three Chang graphs, which are easily seen to have 3-claws.
\qed

Remark. Seidel \cite{S} shows that strongly regular graphs with smallest
eigenvalue $-2$ and $v \ne 2k+4$ do not contain 3-claws. For a discussion
of the relation with line graphs (where the above examples are mentioned
already), see \cite{S2}.

\begin{Theorem}
Let $\Gamma$ be a distance-regular graph of diameter $d \ge 3$
without induced $K_{1,3}$. Then $\Gamma$ is one of:

\noindent
(i) The icosahedron.

\noindent
(ii) A polygon.

\noindent
(iii) The line graph of a Moore graph.

\noindent
(iv) The flag graph of a regular generalized $d$-gon of order $(s,s)$
for some $s$.

\end{Theorem}

\Proof

We see that $\mu$-graphs must be complete, so if $\mu > 1$ our graph is a
Terwilliger graph, and by the discussion of \cite{BCN}, \S 1.16
it follows that $\Gamma$ must be the icosahedron.
(Indeed, since $\mu > 1$ the local graphs of $\Gamma$ are connected of diameter 2.
Now 1.16.1 and 1.16.2 imply that the reduced local graphs of $\Gamma$ are
strongly regular. By repeatedly taking reduced local graphs, we obtain
a strongly regular graph with $\mu = 1$ and without 3-cocliques.
The only such graph is the pentagon. But a graph that is locally
a clique extension of the pentagon, must be locally a pentagon,
and hence is the icosahedron.)

On the other hand, if $\mu = 1$, then we see that $\lambda$-graphs must be complete,
and that $k = 2(\lambda + 1)$, so that $\Gamma$ is a line graph.
Now the classification is given by \cite{BCN}, Theorem 4.2.16.
\qed

\bibliographystyle{plain}
\begin{thebibliography}{}

\bibitem[BCN]{BCN} A.E. Brouwer, A.M. Cohen \& A. Neumaier,
{\it Distance-regular graphs\/}, Springer, 1989.

\bibitem[1]{S} J.J. Seidel,
{\it Strongly regular graphs with $(-1,1,0)$ adjacency matrix having
eigenvalue 3\/}, Lin. Alg. Appl. {\bf 1} (1968) 281-298.

\bibitem[2]{S2} J.J. Seidel,
{\it Configuraties}, pp. 3-50 in: Colloquium Discrete Wiskunde,
J.H. van Lint, J.J. Seidel, P.C. Baayen, Math. Centr. Syllabus 5,
Amsterdam, 1968.

\end{thebibliography}
\end{document}
