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

\def\union{{\cup\,}}

\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}

\title{Hamiltonian strongly regular graphs}
\author{A. E. Brouwer \& W. H. Haemers}
\date{2008-03-04}

\begin{document}
\maketitle


\abstract{
\noindent
We give a sufficient condition for a distance-regular graph
to be Hamiltonian. In particular, the Petersen graph is the
only connected non-Hamiltonian strongly regular graph
on fewer than 99 vertices.
}

\section{Introduction}

For a graph $\Gamma$, let $\alpha(\Gamma)$ denote the independence number
(the maximum size of an independent set) and let $\kappa(\Gamma)$ denote
the vertex connectivity (the minimum number of vertices one has to remove
from $\Gamma$ in order to disconnect it;
note that the graph without vertices is not connected).

Chv\'atal \& Erd\H{o}s~\cite{ChvatalErdos} proved that every
graph $\Gamma$ on at least three vertices, with
$\alpha(\Gamma) \le \kappa(\Gamma)$ is Hamiltonian.
Hoffman showed (cf.~\cite{BCN}, 1.3.2) that every regular graph
$\Gamma$ on $n$ vertices with valency $k$ ($k>0$) and smallest
eigenvalue $s$ satisfies $\alpha(\Gamma) \le -ns/(k-s)$.
It follows that every $k$-regular $k$-connected graph on $n > 2$ vertices
with ${-ns / (k-s)} < k+1$ is Hamiltonian.

However, for many interesting $k$-regular $k$-connected graphs
we have $-ns/(k-s) = k+1$.
This includes the Petersen graph (which has $(n, k, s) = (10, 3,-2)$).
Here we show:
%
\begin{theorem}
Let $\Gamma$ be a $k$-regular $k$-connected graph with $n$ vertices
and smallest eigenvalue $s$ which is not the Petersen graph.
If $k > 1$ and $-ns \leq (k + 1)(k - s)$ then $\Gamma$ is Hamiltonian.
\end{theorem}
%
Brouwer \& Koolen~\cite{BroKoo} proved that every non-complete
distance-regular graph of degree $k$ is $k$-connected. Hence
%
\begin{corollary}\label{distreg}
Let $\Gamma$ be a $k$-regular distance-regular graph with $n$ vertices
and smallest eigenvalue $s$ which is not the Petersen graph.
If $k > 1$ and $-ns \leq (k + 1)(k - s)$ then $\Gamma$ is Hamiltonian.
\end{corollary}
%
Several distance-regular graphs satisfy this inequality
(and some with equality). For connected strongly regular graphs
(i.e., distance regular graphs of diameter 2), this becomes
%
\begin{corollary}
Let $\Gamma$ be a connected strongly regular graph
with parameters $(n,k,\lambda,\mu)$ and smallest eigenvalue $s$.
If $s$ is not integral, or if $-s \le \mu + 1$, then $\Gamma$ is Hamiltonian.
% or, equivalently, $k \le (\lambda+1)\mu$
\end{corollary}
%
(Here $\mu$ is the number of common neighbors of two nonadjacent vertices.)
% (Notation for strongly regular graphs is standard, see, e.g.,
% \cite{BCN}, \S1.3.)
This corollary covers most admissible parameter sets for
strongly regular graphs. We conjecture that the Petersen graph
is the only connected strongly regular graph that is not Hamiltonian.

\medskip
An important ingredient of the proof of the theorem is the following
characterization of the case of equality in Hoffman's bound
(cf.~\cite{BCN}, 1.3.2).
%
\begin{lemma}\label{hoffman}
Let $\Gamma$ be a $k$-regular graph ($k>0$) with $n$ vertices and smallest
eigenvalue $s$. Then $\alpha(\Gamma) \leq -ns/(k-s)$.
A coclique $S$ satisfies the bound with equality,
if and only if every vertex not in
$S$ is adjacent to exactly $-s$ vertices of $S$.
\end{lemma}
%

\section{Rearranging cycles}

Suppose the graph $\Gamma$ is connected and non-Hamiltonian, with
at least one cycle.
Let $C$ be a longest cycle.
Provide $C$ with a cyclic order, and write $x^+$ (resp. $x^-$)
for the successor (predecessor) of $x$ on $C$.
Write $D^+$ (resp. $D^-$) for $\{u^+ \mid u \in D \}$
(resp. $\{u^- \mid u \in D \}$) for any subset $D$ of $C$.
When describing subpaths of $C$, use $u...v$ for the path
from $u$ to $v$ in the cyclic order of $C$, and $u,,,v$ for
the path from $u$ to $v$ in the opposite direction.
For a set of vertices $X$, let $N(X)$ be the set of vertices
not in $X$ but with a neighbor in $X$.
%
Let $H$ be a component of $\Gamma \setminus C$.
Let $K = N(H)$. Then $K \subseteq C$.

(i) If $u,v \in K$ and $v = u^+$, then $uHv...u$ is a longer cycle,
if $uHv$ denotes a path joining $u$ and $v$ via vertices
(at least one) in $H$. Contradiction.
So, $K \cap K^- = K \cap K^+ = \emptyset$
and $K$ is a vertex cut of $\Gamma$ and
$|K| = |K^+| = |K^-| \ge \kappa(\Gamma)$.

(ii) If $u,v \in K$ and $u^+$ is adjacent to $v^+$, then
$uHv,,,u^+v^+...u$ is a longer cycle, contradiction.
So $K^+$ (and $K^-$) are cocliques nonadjacent to any point
of $H$, and $\alpha(\Gamma) \ge |K| + \alpha(H)$.
This argument proves the Chv\'atal-Erd\H{o}s theorem.

% Now assume that $\Gamma$ is regular of degree $k$,
% and $\kappa(\Gamma)=k=\alpha(\Gamma)-1=-ns/(k-s)-1$.
% Then $\alpha(H)=1$, so $H$ is a clique.
% Also assume that $s<-2$, then by Lemma~\ref{hoffman},
% every vertex outside a maximum coclique $S$ has
% at least three neighbors in $S$.

\medskip\noindent
Now assume that $\alpha(\Gamma) = \kappa(\Gamma) + 1$.
Then $\kappa(\Gamma) = |K|$ and $\alpha(H) = 1$, so $H$ is a clique.
Assume moreover that whenever $S$ is a coclique of size $\alpha(\Gamma)$,
each vertex outside $S$ has at least two neighbors in $S$.
\\[5pt]
{\bf Claim:} $|C| = n-1$.
\\
{\bf Proof.}
Suppose $h,h' \notin C$, with $h \in H$, and
consider the coclique $S = K^+\union\{h\}$ of size $\alpha(\Gamma)$.
Since $h' \notin S$ the vertex $h'$ has at least two neighbours in $S$.
Since $K \cap K^+ = \emptyset$, it follows that $h'$ belongs to
a component $H' \ne H$ of $\Gamma \setminus C$ and has
two neighbors $u^+$ and $v^+$ in $K^+$.
But now $uhv,,,u^+h'v^+...u$ is a longer cycle.
Contradiction. \qed
\\
Assume that $\Gamma$ is not a complete bipartite graph $K_{t,t+1}$.
Put $H = \{h\}$.
\\[5pt]
{\bf Claim:} $K^+ \cap K^- = \emptyset$.
\\
%
{\bf Proof.}
Suppose $a = u^+ = v^-$ with $u,v \in K$.
Then $C' = hv...uh$ is another maximum cycle, missing $a$.
Let $A$ be the set of neighbors of $a$.
Assume there exists a $w\in K \setminus A$.
The set $S = A^- \cup \{h\}$ is a coclique of size $\alpha(\Gamma)$,
and $w^- \notin S$, and $w^- \notin K$,
so $w^-$ has at least one neighbor $b$ in $A^-\setminus\{a\}$.
If $b$ lies between $a$ and $w$, then
$hw...ab^+...w^-b,,,vh$ is a longer cycle.
If $b$ lies between $w$ and $a$, then
$hw...bw^-,,,ab^+...uh$ is a longer cycle.
So there is no such vertex $w$, and hence $K = A$.

If $K^+ = K^-$ then $\kappa(\Gamma) = (n-1)/2$.
Since each vertex has at least $\kappa(\Gamma)$ neighbours,
$\Gamma$ is $K_{t,t+1}$, which was excluded.

Hence we may assume that $v$ was chosen such that
$v^+ \in K^+\setminus K^-$.
Let $w$ be the first vertex in $C$ after $v$
such that $w^- \in K^-\setminus K^+$.
Now $w^-$ has at least two neighbors in $K^+\union\{h\}$,
so certainly one neighbor $x^+\in K^+$ is different from $v^+$
and hence lies between $w$ and $a$.
But now $hw...xa,,,x^+w^-,,,vh$ is a longer cycle, contradiction. \qed
\\
Now assume that whenever $S$ is a coclique of size $\alpha(\Gamma)$,
each vertex outside $S$ has at least three neighbors in $S$.
\\[5pt]
Call an edge $\{a,b\}\in E(\Gamma)$ a {\em special cord} of $C$
if $a,b \in C$, $\{a,b\}\notin E(C)$, and $a$ or $b$ lies in $K^+ \cup K^-$.
The {\em length} of a special cord $\{a,b\}$ is the length of the shortest
(undirected) path between $a$ and $b$ via $C$.
Let $\{a,b\}$ be a special cord of minimum length for a cycle $C$,
where the minimum is taken over all possible special cords and maximum cycles.
Assume that $C$ is oriented from $a$ to $b$.

If $a^+ \notin K^+$ then there is a
vertex $u^+ \in K^+ \setminus \{a,a^{++}\}$, adjacent to $a^+$.
Since $\{a,b\}$ is a minimal special cord, $u^+$ is not in $a...b$.
Similarly, if $b^-\notin K^+$ there is
a vertex $v^+ \in K^+ \setminus \{b^{--},b\}$ adjacent to $b^-$,
but not in $a...b$.
Now $hu,,,v^+b^-,,,a^+u^+...ab...vh$ or
$hv,,,u^+a^+...b^-v^+...ab...uh$ is a longer cycle.

In a similar way we find a longer cycle if $a^+\notin K^-$ and
$b^-\notin K^-$.
It is impossible that $a^+\in K^+$ and $b^-\in K^-$
because $K \cap (K^+ \cup K^-) = \emptyset$.
Therefore $a^+\in K^-$, $b^-\in K^+$ and $a\in K^+$ or $b \in K^-$.
By symmetry, we may assume $a \in K^+$.

Now $C'=ha^-,,,ba...b^{--}h$ is another maximum cycle, missing $b^-$.
If $a^{++}\neq b^{--}$, then $C'$ has a special cord $\{a^{++},h\}$,
which is shorter than the special cord $\{a,b\}$ of $C$, contradiction.
So $a^{++} = b^{--}$.
(Note that the Petersen graph has this structure.)
Let $E$ be the set of neighbors of $b^-$ distinct from $b,b^{--}$.
Then $S = E^- \cup \{b^-,a,h\}$ is a coclique of size $\alpha(\Gamma)$.

We have $a^+ \in K^-$, so $a^+$ has a neighbor $u^+$
in $K^+\setminus\{a\}$.
Now $C'' = ha^-,,,u^+a^+ab...uh$ is a circuit of length $n-2$
missing $b^{--}$ and $b^-$.

Since $b^{--} \notin S$,
it follows that $b^{--}$ has a neighbor $c^- \in E^-$.
Now $P= cb^-b^{--}c^-$ is a path of length 3.
Since $b^- \in K^+$ we have $c\neq u^+$ so
$\{c^-,c\}$ is an edge of $C''$. Replacing this edge by $P$ gives a
Hamiltonian circuit. This proves:
%
\begin{proposition}
Suppose that $\alpha(\Gamma) \le \kappa(\Gamma)+1$, and
that each vertex outside any coclique $S$ of size $\alpha(\Gamma)$
has at least $3$ neighbours in $S$.
Then $\Gamma$ is Hamiltonian, or $\Gamma$ is $K_{t,t+1}$ (with $t \ge 2$).
\qed
\end{proposition}

\begin{corollary}\label{rc}
Let $\Gamma$ be a $k$-regular and $k$-connected graph with smallest
eigenvalue $s<-2$.
If $-ns/(k-s) \leq k+1$, then $\Gamma$ is Hamiltonian. \qed
\end{corollary}

\section{Smallest eigenvalue $-2$}

Suppose $\Gamma$ is $k$-regular with smallest eigenvalue $-2$.
Then $\Gamma$ is a line graph or belongs to a finite list of 187
so called regular exceptional graphs (see~\cite{BCS} or \cite{CRS}).
These graphs and their spectra are known (\cite{CRS}, Table~A3).
For these graphs Hoffman's coclique bound equals $2n/(k+2)$, and
for only five cases this number is equal to $k+1$.
All five have $n=10$ and $k=3$ (see \cite{CRS}, p.\,218 for the
drawings of these five graphs).
One is the Petersen graph, but the other four
are easily seen to be Hamiltonian. So we can conclude:
%
\begin{proposition}
The Petersen graph is the only non-Hamiltonian $k$-regular
exceptional graph with a coclique of size $k+1$.
\end{proposition}
%
Next we deal with the case that $\Gamma$ is a $k$-regular line graph.
%
\begin{proposition}
A $k$-connected $k$-regular line graph $\Gamma$ on $n$ ($n\geq 3$)
vertices satisfying $\alpha(\Gamma) = 2n/(k+2) \leq k+1$, is Hamiltonian.
\end{proposition}
%
{\bf Proof.}
Let $\Gamma$ be the line graph of $\Gamma'$ with $n'$ vertices.
Note that a coclique in $\Gamma$ corresponds to a matching in
$\Gamma'$.
It is well-known that $\Gamma'$ is either regular or
bipartite biregular.
Assume $\Gamma'$ is bipartite biregular.
Let $n_1'$ and $n_2'$ ($n_1' \leq n_2'$) be the sizes of the two parts
with degrees $k_1'$ and $k_2'$, respectively.
Then $k=k_1'+k_2'-2$, $n = n_1'k_1' = n_2'k_2'$, and $k_1' \geq k_2'$.
Clearly, a matching in $\Gamma'$ has at most $n_1'$ edges, so
$\alpha(\Gamma)\leq n_1'$. On the other hand,
$2n/(k+2) = 2n_1'k_1'/(k_1'+k_2') \geq  n_1'$ with equality only if
$k_1' = k_2'$.
This shows that $\Gamma'$ is regular (of degree $k'$ say).

A sequence $(e_1,\ldots,e_{\ell})$ of $\ell$ distinct edges of a graph is
called {\it sequential} if $e_i$ and $e_{i+1}$ intersect
for $i=1,\ldots,\ell-1$.
A graph is called {\it sequential} if it admits a sequential sequence
$(e_1,\ldots,e_m)$ consisting of all edges, such that $e_1$ intersects $e_m$.
It is clear that a graph is sequential if and only if its line graph
is Hamiltonian.
We will show that $\Gamma'$ is sequential.
If $k'$ is even, then $\Gamma'$ is Eulerian and therefore sequential.
So assume that $k'$ is odd.
Note that $n = n'k'/2$ and $k = 2(k'-1)$.
Since $\alpha(\Gamma)=2n/(k+2)=n'/2$,
$\Gamma'$ has a perfect matching $M$ (say).
Consider the graph $\Gamma''$, obtained from $\Gamma'$
by deleting $M$.
If $\Gamma''$ is connected, $\Gamma''$ is Eulerian, and $\Gamma'$ is
easily seen to be sequential.
If $\Gamma''$ is not connected, it consists of two
disjoint $(k'-1)$-regular components, both with $n'/2$ vertices,
and all edges of $M$ meet both components.
(Indeed, since $\Gamma$ is $k$-connected,
and $n'/2 = \alpha(\Gamma) \le k+1$,
$\Gamma'$ cannot be separated by removing fewer than $n'/2$ edges.)
The two components $\Gamma_1$ and $\Gamma_2$ of $\Gamma''$ are Eulerian.
%
% Note: perhaps $\Gamma'$ is the Petersen graph and
% $\Gamma_1$ and $\Gamma_2$ are pentagons.
%
Consider two edges $\{w,x\}$ and $\{y,z\}$
from $M$ such that $\{x,y\}$ is an edge in $\Gamma_2$.
From an Eulerian cycle of $\Gamma_2$ one easily constructs a sequential
sequence $S$ of $\Gamma'$, such that $S$ contains all edges of $\Gamma_2$
and $M$, starts with $\{w,x\}$ and ends with $\{y,z\}$.
If $\{w,z\}$ is an edge of $\Gamma_1$ we can insert $S$ in
an Eulerian tour in $\Gamma_1$ right before or after $\{w,z\}$
and find that $\Gamma'$ is sequential.
%
% If this never happens, then $\Gamma_1$ and $\Gamma_2$ are complementary.
%
If $w$ and $z$ are not adjacent, they have a common neighbor $v$ in $\Gamma_1$
(since $2k' > n'/2$). Now consider the graph obtained from $\Gamma_2$
by deleting the edges $\{v,w\}$ and $\{v,z\}$ and adding the edges
$\{w,x\}$ and $\{x,y\}$ and $\{y,z\}$. Now we can insert $S$ in
an Eulerian tour of this latter graph, minus the three added edges,
and also insert the two removed edges again, and find that
$\Gamma'$ is sequential.
\qed\\
%
The two propositions above together with the theorem of
Chv\'atal and Erd\H{o}s prove the main theorem if $s=-2$.
If $s=-1$, then $\Gamma=K_n$, and the result is trivial.
With Corollary~\ref{rc}, this completes the proof of the main theorem.

\section{Examples}
Several distance-regular graphs of small diameter
satisfy the inequality of Corollary \ref{distreg}.
%
An interesting infinite family consists of the collinearity graphs of
generalized quadrangles $GQ(r,t)$ from which a spread has been deleted
(see \cite{BCN}, p.\,385).
These graphs have diameter 3 and $(n,k,s)=((r+1)(rt+1),rt,-t)$.
They satisfy the condition (with equality), and hence are Hamiltonian.
The smallest of these has $r=t=2$, and is isomorphic to the line graph of
the Petersen graph.
%
% Also equality: Johnson J(16,3) and J(9,4).
% And inequality: J(m,3), m < 16, and J(8,4).
%

The distance-regular graphs with diameter 2 are precisely
the connected strongly regular graphs. For these graphs the
connectivity was determined already in \cite{BroMes}.
Only few parameter sets for connected strongly regular graphs have
$-s > \mu+1$. For $n\leq 100$ there are only five cases:

\medskip
\begin{tabular}{llcll}
\# & $(v,k,\lambda,\mu)$ & $s$ & name & Hamiltonian \\
\hline
1 & (50,7,0,1) & $-3$ & Hoffman-Singleton graph & yes \\
2 & (56,10,0,2) & $-4$ & Gewirtz graph & yes \\
3 & (77,16,0,4) & $-6$ & $M_{22}$ graph & yes \\
4 & (99,14,1,2) & $-4$ &  & ? \\
5 & (100,22,0,6) & $-8$ & Higman-Sims graph & yes \\
\end{tabular}

\medskip
In cases 1, 2, 3 and 5 there is a unique strongly regular graph
with the given parameters, and the graph is Hamiltonian by
direct verification.
(In case 5 Hamiltonicity also follows from the fact that
the smallest eigenvalue has multiplicity 22, so that $\alpha \le 22$.)

In case 4, existence of a strongly regular graph is open.
Thus, all connected strongly regular graphs on fewer than 99 vertices
are Hamiltonian.

We conjecture that the Petersen graph is the only
connected non-Hamiltonian strongly regular graph.

\begin{thebibliography}{9}

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

\bibitem{BroMes}
A. E. Brouwer \& D. M. Mesner,
{\it The connectivity of strongly regular graphs},
Europ. J. Combin. {\bf 6} (1985) 215--216.

\bibitem{BroKoo}
A. E. Brouwer \& J. H. Koolen,
{\it The vertex-connectivity of a distance-regular graph},
Europ. J. Combin. (to appear).

\bibitem{BCS} F. C. Bussemaker, D. Cvetkovi\'c \& J. J. Seidel,
{\it Graphs related to exceptional root systems},
T. H. Report 76-WSK-05, Technical University Eindhoven, 1976.

\bibitem{ChvatalErdos}
V. Chv\'atal \& P. Erd\H{o}s,
{\it A note on Hamiltonian circuits},
Discr. Math. {\bf 2} (1972) 111--113.

\bibitem{CRS} D. Cvetkovi\'c, P. Rowlinson \& S. Simi\'c,
{\it Spectral Generalizations of Line Graphs: On graphs with
least eigenvalue $-2$}, Cambridge Univ. Press, 2004.

\end{thebibliography}

\end{document}
