

In this section we mention some important open problems. The most
important one is to classify all distance-regular graphs of large
enough diameter.

\subsection{The classification of distance-regular graphs of large diameter}

We first restrict the classification of distance-regular graphs to
the following three problems.

\begin{problem} Classify the $Q$-polynomial distance-regular graphs with large enough
diameter. \end{problem}

\begin{problem}
Classify the geometric distance-regular graphs with large
enough diameter.\end{problem}

\begin{problem}\label{problem:3}
Prove or disprove the following conjecture of Bannai and Ito
\cite[p.~312]{bi}: A primitive distance-regular graph with large
enough diameter is $Q$-polynomial.\footnote{This conjecture is true
in the case of distance-transitive graphs and also for thick
regular near polygons with $c_2 \geq 3$ and diameter at least $4$.
On the other hand, the recent construction of an infinite family of
imprimitive cometric but not metric association schemes by
Moorhouse and Williford \cite{Williford2014AGT} may be relevant to
disproving the dual version of this conjecture on cometric
association schemes (which was also raised by Bannai and Ito,
see Section \ref{sec:2Qpol}); cf. Section
\ref{sec:cometricschemes}.}
\end{problem}

\subsection{General problems}

\begin{problem} Generalize results on distance-regular graphs to larger classes of
graphs; for example, the Delsarte clique bound.
\end{problem}


\begin{problem} Which results on distance-regular graphs can be dualized to cometric association
schemes? See Section \ref{sec:cometricschemes}.
\end{problem}



Below, we will give a list of more specific (and typically smaller)
problems related to the classification of distance-regular graphs.


\subsection{\texorpdfstring{$Q$-polynomial}{Q-polynomial} distance-regular graphs}

The $Q$-polynomial distance-regular graphs fall into types I, IA,
II, IIA, IIB, IIC, and III from
\cite{bi}.
In Section \ref{Q-classification}, we showed that type IA cannot occur and that the distance-regular graphs
of types IIA, IIB, IIC, and III are completely determined.
For type II, the classification is known for $D\geq 14$.

\begin{problem} \begin{enumerate}[(i)]
\item Determine the graphs of type II with $D \leq 13$.
\item Determine the $Q$-polynomial distance-regular graphs of type I. A
subproblem is to determine the distance-regular graphs with classical
parameters with $b \neq 1$.
\end{enumerate}
\end{problem}

The classification of imprimitive $Q$-polynomial distance-regular
graphs is complete for $D\geq 12$, except for the classification of
the distance-regular graphs with the same intersection array as the
bipartite dual polar graphs. See Sections
\ref{sec:bipartiteDRG} and \ref{sec:antipodalDRG}.

\begin{problem} Classify the
graphs that have the same intersection array as the bipartite dual
polar graphs and the Hemmeter graphs for $D \geq 12$. Also, improve
the condition $D\geq 12$ for the bipartite case.
\end{problem}

\begin{problem}
Show that a $Q$-polynomial distance-regular graph with diameter $D$ is imprimitive if and only if $a_D = 0$.
\end{problem}

Lang and Terwilliger \cite{LT2007EJC} almost classified the $Q$-polynomial generalized odd graphs with diameter at
least three, leaving open one set of intersection arrays for $D=3$. See Section \ref{sec:Qalmostbipartite}.

\begin{problem} Classify the $Q$-polynomial generalized odd graphs with diameter three.
\end{problem}

\begin{problem}\label{prob:2P+Q}
Classify the primitive $Q$-polynomial distance-regular graphs with two
$P$-polynomial orderings and diameter three or four. See Section
\ref{sec:2Porder}. \end{problem}

\begin{problem} Classify the primitive distance-regular graphs with two
$Q$-polynomial orderings and diameter three. %or four %%% by Koolen and Ma.
See Section \ref{sec:Qmultipleordering}.\end{problem}

\begin{problem}
Let $\eta_0, \eta_1, \ldots, \eta_D$ be a $Q$-polynomial ordering of the eigenvalues (that is, of the
corresponding idempotents), and let $\theta_0 > \theta_1 > \cdots > \theta_D$ be the natural ordering of the eigenvalues.
What can be said of the relation between the $\eta_i$ and the $\theta_j$?
For example, determine whether $\eta_1 \in \{ \theta_1, \theta_D, \theta_{D-1}\}$,
or whether $\{\theta_1, \theta_D\} \cap \{\eta_1, \eta_D\} \neq \emptyset $.
(For bipartite graphs and antipodal graphs, see \cite{Caughman1998GC,Pascasio1999JAC} and also Section \ref{sec:antipodalDRG}.)
\end{problem}

\begin{problem}
Classify the tight $Q$-polynomial distance-regular graphs with $D=4$.
\end{problem}


\subsection{Vanishing Krein parameters}

Bannai and Ito \cite[p.~312]{bi} conjectured that primitive
distance-regular graphs with large enough diameter are
$Q$-polynomial (see Problem \ref{problem:3}), and
so for such graphs most Krein parameters vanish.

\begin{problem}\label{problem:primalof}
Show that there exists a constant $C$ such that for every primitive distance-regular graph there exists a primitive idempotent, say, $E_1$, such that $|\{j:q_{1j}^i\ne 0\}|\leq C$ for all $i$.
\end{problem}

Note that this problem is dual to Problem \ref{problem:dualof}.



\begin{problem} Let $\theta_i$ be a tail (see Section \ref{sec:Qpolcharacterizations}). \begin{enumerate}[(i)]
\item  Determine whether $\theta_i \in \{\theta_1, \theta_D, \theta_{D-1}\}$. This last case ($\theta_i=\theta_{D-1}$)
    should only occur for bipartite distance-regular graphs.
\item Determine $j\ne 0,i$ such that $q^j_{ii} \neq 0$.
\item Is it possible to classify the distance-regular graphs with a light tail? Besides the antipodal $Q$-polynomial
    distance-regular graphs, there seem to be only the halved cubes and the Hermitian dual polar graphs
    $^2\A_{2D-1}(\sqrt{q})$.
\end{enumerate}
\end{problem}

\begin{problem} Sometimes, one can use the absolute bound to show that some Krein parameters vanish,
if one of the non-trivial eigenvalues has a small multiplicity.
\begin{enumerate}[(i)]
\item Find more conditions that imply that some Krein parameters vanish.
\item Study distance-regular graphs with no vanishing (non-trivial) Krein
parameters. Among the primitive distance-regular graphs with diameter three that are not
$Q$-polynomial, there are few that have a vanishing (non-trivial) Krein
parameter (we checked that there is only one on at most 100 vertices: the
Sylvester graph).
\end{enumerate}
\end{problem}

\begin{problem}
Juri\v{s}i\'{c}, Coolsaet, and others have used vanishing Krein parameters to show that certain families of intersection arrays are not feasible, and also to show the uniqueness of some distance-regular graphs by their intersection arrays.
See Section \ref{sec:triple intersection numbers}.
But it is not known when the method of vanishing Krein parameters gives enough extra information in order to decide the non-existence of certain intersection arrays.
Explore this.
\end{problem}


\subsection{Classical parameters}
\begin{problem} Characterize the classical distance-regular
graphs by their intersection arrays. \end{problem}

\begin{problem}
Show that $Q$-polynomial geometric distance-regular graphs which are not polygons have classical parameters.
\end{problem}

\begin{problem} Decide whether the Grassmann graphs $J_q(2D,D)$ are determined by their intersection
arrays. See Section \ref{sec:clasfamilies}. Decide whether there are other
distance-regular graphs than the twisted Grassmann graphs with the same
intersection arrays as the Grassmann graphs $J_q(2D+1,D)$.
\end{problem}

The following problem was posed by Vanhove in his thesis \cite[Pr.~8]{Vanhove2011PhD}.

\begin{problem}
Determine whether all distance-regular graphs with classical parameters
$(D, b, \alpha, \beta) = (D,-q,-(q + 1)/2,-((-q)^D + 1)/2)$, $q$ odd, are
subgraphs of the Hermitian dual polar graph $^2\A_{2D-1}(q)$ (for sufficiently large $D$).
See Theorem \ref{thm:b<-1} and the paragraph that follows it.
\end{problem}

\subsection{Geometric distance-regular graphs}

\begin{problem} Determine whether for a given integer $m \geq 2$, there are only finitely many
geometric distance-regular graphs with $D \geq 3$, $c_2 \geq 2$, and smallest eigenvalue $-m$, besides the Grassmann
graphs, Johnson graphs, bilinear forms graphs, and Hamming graphs. See Section \ref{sec:fixedsmallestev}. Note that the
generalized $2D$-gons of order $(q,1)$ for $D=3,4,6$ (which exist for all prime powers $q$) are geometric with smallest
eigenvalue $-2$, but they have $c_2 =1$; see also \cite[Thm.~4.2.16]{bcn}.\end{problem}

\begin{problem}
Classify the geometric distance-regular
graphs with $a_1 \geq 1$ and $c_2 \geq 2$.
\end{problem}

\begin{problem}
Classify the (non-bipartite) geometric distance-regular graphs that are also $Q$-polynomial.
\end{problem}

Let $\G$ be a geometric distance-regular graph with respect to a set of cliques $\cal C$. We call an induced subgraph $\Delta$ of $\G$ {\em a subspace}  if $\Delta$ is closed and for each edge $xy$ contained in
$\Delta$,  all the vertices of the clique $C \in {\cal C}$ containing $x$ and $y$ are in $\Delta$.

\begin{problem} Find sufficient and necessary conditions for the existence of subspaces, in a similar fashion as the $m$-boundedness condition. See Section \ref{sec: subgraphs}.
\end{problem}


\begin{problem} Classify the geometric distance-regular graphs having the property that for each pair of distinct vertices $x$ and $y$ there exists a (unique) subspace $\Phi(x,y)$ of diameter $d(x,y)$. This would be an
extension of the classification of thick regular near polygons with $c_2 \geq 2$.\end{problem}


\begin{problem} Complete the classification of thick regular near polygons with diameter at least $4$ and $c_2 \geq 2$. Only the case $c_2 =2$
and $c_3 >3$ needs to be considered. The case $c_2=1$ seems to be too difficult at the moment. See also Theorem
\ref{thm:RNPthick}.
\end{problem}


\begin{problem}
Let $\G$ be a geometric distance-regular graph with respect to $\cal C$. Define the dual graph on
vertex set $\cal C$, where two cliques are adjacent if they intersect. Determine when this dual graph is
distance-regular (this happens for the Johnson graphs and the Grassmann graphs).
\end{problem}

\subsection{The Bannai-Ito conjecture}

The Bannai-Ito conjecture can be interpreted as a diameter bound in terms of the valency, but the current proof (cf.~Section \ref{sec:proofBIconjecture}) gives a very bad bound.
On the other hand, all the known distance-regular graphs with valency $k$ at least three have $D \leq 2k+2$,
with equality only for the Foster graph.

\begin{problem}  Find a good diameter bound in terms of the valency.
\end{problem}

\begin{problem} Let $\G$ be a distance-regular graph with diameter $D$, head $h$, and valency $k$ at least three.
\begin{enumerate}[(i)]
\item Prove Ivanov's conjecture that $\ell(c_i, a_i, b_i) \leq h+1$ \cite[p.~191]{bcn},
\item Show that $D \leq (2k-3)h + 1$ except if $\G$ is the dodecahedron (in which case $D =5$, $h =1$, and $k=3$),
\item Show that if $c_i \geq 2$ for some $i$ then $|\{i : c_i = c\}| \leq \min \{i : c_i \geq 2\} - 1$ for $c=2,3,\dots, k-1$. See
    also Proposition \ref{BHKprop}.
\end{enumerate}
\end{problem}

All the
known distance-regular graphs except for the polygons have $h \leq 5$, with equality for the generalized
dodecagons.

\begin{problem}
Prove the conjecture of Suzuki \cite[Conj.~1.5.2]{Su99} that claims that there exists a constant $H$ such that all
distance-regular graphs with valency at least three have head $h \leq H$. \end{problem}

\begin{problem}
Suzuki's conjecture in the above problem would imply that the girth of a distance-regular graph is bounded. Prove the more specific (unpublished) conjecture by Koolen and Suzuki that the girth of a distance-regular graph with valency at least three is at most $12$.
\end{problem}

\begin{problem}
Show that every distance-regular graph with valency and diameter at least three has an
integral eigenvalue besides the valency. This was posed as a question by `BCN' \cite[p.~130]{bcn}. Clearly this is the case for bipartite distance-regular graphs and more
generally for geometric distance-regular graphs.
\end{problem}

\begin{problem}
Define the degree of an algebraic integer as the degree of its minimal polynomial. All the
eigenvalues of the known distance-regular graphs have degree at most three; with the
Biggs-Smith graph as the only example having an eigenvalue with degree equal to three. In this light we propose the following conjecture: {\em Every eigenvalue of
a distance-regular graph with valency at least three has degree at most three.} This conjecture could be a first step to
show the above conjecture of Suzuki.\end{problem}

\begin{problem} Develop theory for distance-regular graphs
with only integral eigenvalues. It is easy to show that for such graphs the diameter $D$ is bounded by $2k$, where $k$ is the valency.
%But for example the case $D = 2k$ should not be possible. Show this.
If possible, improve this bound.
Also obtain a good bound for the head.
\end{problem}


\subsection{Combinatorics}

\begin{problem} Classify the $1$-homogeneous distance-regular graphs that are not bipartite nor a generalized odd graph. See Section
\ref{sec:homogeneity}.\end{problem}



\begin{problem}
Study distance-regular graphs that are locally strongly regular.
\end{problem}

\begin{problem} Determine whether $k_i = k_j$ for some distinct $i$ and $j$ with
$i+j \leq D$ and $k_D \geq 2$ implies that $k=2$. See Section
\ref{sec:charantipodal}.\end{problem}

\begin{problem} Given an integer $\alpha \geq 1$, determine whether there are only finitely many
distance-regular graphs with diameter at least three and $a_1 > \alpha$ such
that each local graph has second largest eigenvalue at most $\alpha$. See
Section \ref{sec:DIAMETEReigenvalues}.\end{problem}

It is known that if $c_2 \geq 2$ then $c_3 > c_2$ \cite[Thm.~5.4.1]{bcn}.

\begin{problem} Show that if $c_2 \geq 2$, then the $c_i$
are strictly increasing. \end{problem}

\begin{problem} Determine whether one needs to remove at least $2k - 2 - a_1$ vertices
in order to disconnect a distance-regular graph with diameter at least three
such that each resulting component has at least two vertices. Note that if this
is the case, then this is best possible because $2k - 2 - a_1$ is the size of the neighborhood
of an edge. Cioab\u{a}, Kim, and Koolen \cite{CKK12} showed that it is not
true for strongly regular graphs, but it is believed it may be true for strongly regular graphs
with $k \geq 2a_1 +3$.\end{problem}

In Section \ref{sec:2Porder} we discussed distance-regular graphs $\G$ with multiple $P$-polynomial orderings.

\begin{problem}\begin{enumerate}[(i)]
\item Classify the generalized odd graphs.
\item Determine new putative intersection arrays for generalized odd graphs.
\item Show that if $\G$ is a bipartite antipodal $2$-cover with diameter $2e$ and $e \geq 3$, then $\G$ is a
    $2e$-cube.
\item Classify the non-bipartite antipodal $2$-covers with diameter $D \geq 4$ that have a generalized odd graph as
    folded graph.
\item Show that if $\Delta=\G_{D}$ is also distance-regular with diameter $D$, then $\Delta$ is a generalized odd graph or a Taylor graph.
\end{enumerate}
\noindent
See also Problem \ref{prob:2P+Q}.
\end{problem}

The following problem is due to Fiol \cite[Conj.~3.6]{Fiol2001CPC}.
\begin{problem}
Show that a distance-regular graph with diameter at least $4$ is strongly distance-regular (cf.~Section \ref{sec:spectralexcess}) if and only if it is antipodal.
See Section \ref{sec:distance-D graph}.
\end{problem}

The following problem is due to Pyber \cite[Conj.~1, 3.1]{PyberHam} who showed that all but finitely many strongly regular graphs are Hamiltonian.
%Note that this is closely related to Lov\'{a}sz conjecture that all but finitely many vertex-transitive graphs are Hamiltonian.
%The following problem was communicated to us by Pyber, who showed that all but finitely many strongly regular graphs are Hamiltonian \cite{PyberHam}.
Recall also the well-known Lov\'{a}sz conjecture that all but finitely many connected vertex-transitive graphs are Hamiltonian.
\begin{problem}
\begin{enumerate}[(i)]
%\item Is it true that all but finitely many distance-regular graphs are Hamiltonian?
%\item In particular, is it true that all but finitely many distance-regular graphs with diameter three are Hamiltonian?
\item Show that all but finitely many distance-regular graphs are Hamiltonian.
\item In particular, show that all but finitely many distance-regular graphs with a fixed diameter $D$ are Hamiltonian.
\end{enumerate}
\noindent
The case $D=3$ seems to be the way to attack this problem.
\end{problem}

\begin{problem}
Determine which distance-regular graphs are core-complete.
Currently no distance-regular graphs are known that are not core-complete.
See Section \ref{sec:cores}.
\end{problem}

\begin{problem}\begin{enumerate}[(i)]
\item Show or disprove the conjecture of Neumaier, i.e., that all completely regular codes in the Hamming graphs with minimum distance at least $8$ are known.
\item Neumaier \cite{ Neu92} challenged his readers to classify the completely regular codes in
    the Hamming graphs with $nq \leq 48$. But there are many feasible intersection arrays with small covering radius, say $2$ and $3$.
We therefore would like to modify the challenge to classify the completely regular  codes in the Hamming graphs with $nq \leq 48$ with covering radius at least $4$.
%\item \textcolor{blue}{If a binary completely regular code $C$ of length $n$  has intersection array $\{ \beta_0, \beta_1, \ldots, \beta_{\rho-1}; \gamma_1, \gamma_2, \ldots, \gamma_{\rho}\}$, find the possible lengths of any completely regular non-degenerated binary codes with this intersection array.}
%We note that there are finitely many possibilities for the length. See Section \ref{sec: arithmetic crc}.
%\item Given an intersection array  $\{ \beta_0, \beta_1, \ldots, \beta_{\rho-1}; \gamma_1, \gamma_2, \ldots, \gamma_{\rho}\}$ such that there exists a $q$-ary completely regular code with this intersection array, show that the length of a $q$-ary completely regular non-degenerated code with this intersection array  is bounded above. See Section \ref{sec: arithmetic crc}.
\item Give more results on the intersection array of a completely regular code in a distance-regular graph.
\end{enumerate}
\end{problem}



\subsection{Uniqueness and non-existence}

\begin{problem} Decide whether the Livingstone graph is determined by its
intersection array $\{11,10,6,1;1,1,5,11\}$. See \cite[\S 13.5]{bcn}.\end{problem}




\begin{problem}
Construct a distance-regular graph with intersection array $\{7,6,6; 1,1,2\}$, or show that none exists. See
\cite[p.~148]{bcn}.\end{problem}

\begin{problem} Classify the non-bipartite distance-regular graphs with diameter at least four with the same intersection array as a
regular near polygon. Currently, the only known ones that are not regular near polygons are the Doob graphs. See
Section \ref{sec:rnp}.
\end{problem}

\begin{problem} Classify the distance-regular graphs that are locally Hoffman-Singleton, i.e., those with
intersection arrays $\{ 50, 42, 9; 1, 2, 42\}$ and $\{ 50, 42, 1; 1, 2, 50\}$.
See Section \ref{sec:existencequadranglesT}.\end{problem}

The following problem was raised by Bannai [private communication].
\begin{problem}
Determine whether the following is true:
if a distance-regular graph $\G$ with diameter $D\geq 4$ has intersection numbers $c_i = i^2$ and $b_i = (n-d-i)(d-i)$  for $i \leq D-1$ for some positive integers $n$ and $d$, then $\G$ is the folded Johnson graph with diameter $D$.
Similar problems can be formulated for other classical families of distance-regular graphs.
See, e.g., Theorem \ref{thmquotient} for the case of Hamming and Doob graphs.
\end{problem}


\subsection{The Terwilliger algebra}

\begin{problem}
Determine the structure of the Terwilliger algebra for the four families of forms graphs and also for the twisted Grassmann graphs.
\end{problem}

\begin{problem} Develop theory for $1$-thin distance-regular graphs with exactly three irreducible $\TT$-modules with endpoint $1$ up to isomorphism.
\end{problem}

\begin{problem}
The vectors $\mathbf{f}_t$ (cf.~\eqref{MacLean's vector}) can be defined for any (i.e., not necessarily bipartite) distance-regular graph.
Give more results using the positive semidefiniteness of the Gram matrix of some of the $\mathbf{f}_t$.
For example, is it possible to prove the Terwilliger tree bound (cf.~Section \ref{sec:tree_bound}) in this way?
\end{problem}

\begin{problem} An irreducible $\TT$-module $W$ is called {\em sharp} if $\dim E_t^{\ster} W = 1$, where $t$ is its endpoint.
Give sufficient and necessary conditions such that all the irreducible $\TT$-modules of a distance-regular graph are
sharp.\end{problem}



The following problem was raised by Terwilliger [private communication].

\begin{problem}
Find all the
$2$-thin bipartite distance-regular graphs with diameter $D\geq 4$ with at most two irreducible $\TT$-modules with endpoint $2$ up to isomorphism.
The
$Q$-polynomial bipartite distance-regular graphs are included in this class, and so are the
taut graphs; cf.~Section \ref{sec: Hadamard products}. By a recursion obtained by Curtin \cite{Curtin1999GC}, for these distance-regular graphs
the intersection array is determined by at most four parameters (besides $D$); cf.~Section \ref{sec:thinness}.
A related problem is to find a closed form for the intersection numbers.
\end{problem}

The following three problems were also posed by Terwilliger \cite{Talgebra92,Terwilliger1993N}.

\begin{problem}
Suppose $\G$ is a thin distance-regular graph with diameter $D$ and is not $Q$-polynomial.
Show that if $D$ is sufficiently large then one of the following holds.
\begin{enumerate}[{\textup (i)}]
\item $\G$ is bipartite, and the halved graph is thin and $Q$-polynomial.
\item $\G$ is antipodal, and the folded graph is thin and $Q$-polynomial.
\end{enumerate}
\end{problem}

\begin{problem}
Let $\G$ be a thin non-bipartite $Q$-polynomial distance-regular graph.
Take any two distinct vertices $x,y$.
Show that the minimal convex subgraph containing $x$ and $y$ is a thin $Q$-polynomial distance-regular graph with diameter $d(x,y)$.
If this claim turns out to be false, then find a simple additional assumption on $\G$ under which it is true.
\footnote{That $\G$ is non-bipartite was not assumed in \cite{Terwilliger1993N}. Terwilliger [private communication] pointed out that the Hemmeter graphs (and all distance-regular graphs with the same intersection array as (but not isomorphic to) the bipartite dual polar graphs) provide counterexamples.}
\end{problem}

\begin{problem}
Classify the thin $Q$-polynomial distance-regular graphs.
\end{problem}

The following problem was raised by Ito [private communication].
\begin{problem}
Study the structures of the irreducible $\TT$-modules of $Q$-polynomial distance-regular graphs from the point of view of the theory of tridiagonal systems, in particular as `tensor products' of Leonard systems.
See Section \ref{sec: TD systems}.
Is it true that each of the corresponding tridiagonal systems is a `tensor product' of at most two Leonard systems?
We note that this is indeed true for the irreducible $\TT$-modules with endpoint $1$; see Section \ref{sec:thinness-Q}.
\end{problem}
\begin{problem}
Is the isomorphism class of an irreducible $\TT$-module for a $Q$-polynomial distance-regular graph with $c_2 \geq 2$ and $a_1 \neq 0$ determined by its local eigenvalue and endpoint?
\end{problem}


\subsection{Other classification problems}

\begin{problem} Classify the distance-regular Terwilliger graphs. See Section \ref{sec:existencequadranglesT}.\end{problem}

There are infinitely many putative parameter sets $(v,k,\lambda,\mu)$ for strongly regular graphs with $\mu =1$ and
$\lambda =2$.

\begin{problem} Show that there are only finitely many strongly regular graphs with $\mu =1$. By Proposition \ref{mbounded} ($m=2,h=1$), a consequence of this would be that
there are finitely many distance-regular graphs with $c_3 =1$ and $a_1\neq a_2$. It would also contribute to the
classification of Terwilliger graphs with $\mu \geq 2$ by considering its local graphs. \end{problem}

\begin{problem} Generalize results for strongly regular graphs that do not yet have analogues for distance-regular graphs.\end{problem}

\begin{problem}
Fuglister \cite{Fuglister} uses $\mathrm{mod} \ p$ calculations for the multiplicities to show that if a distance-regular graph
has $D = h+1$, where $h$ is the head, then $h \leq 12$. Suzuki \cite[p.~87]{Su99} claims this can be generalized to the
case $D \leq h+3$. Brouwer and Koolen \cite{BK99} use a similar argument for the generation of feasible arrays for the
distance-regular graphs with valency $4$. Find more instances where this method works.
\end{problem}

\begin{problem}
For a coconnected distance-regular graph $\G$, show that the intersection number $c_2$ is bounded above by a function of $\frac{b_1}{\theta_1 +1}$. For strongly regular graphs, this is true as in that case
$\frac{b_1}{\theta_1 +1}$ is equal to $-\theta_2-1$ and hence it follows by Neumaier's \cite{Neu80} $\mu$-bound. It is also true for distance-regular graphs with $\theta_1 = b_1 -1$ by the classification of such graphs (see \cite[Thm.~4.4.11]{bcn}), as they all have $c_2 \leq 10$.
But even for $Q$-polynomial distance-regular graphs, a bound for $c_2$ in terms of $\frac{b_1}{\theta_1 +1}$ is not known to exist.
\end{problem}




\begin{problem} Classify the distance-regular graphs of order $(s,2)$. For $s=1$ these are precisely the distance-regular graphs with valency three.
For $s=2$, they were classified by Hiraki, Nomura, and Suzuki
\cite{HNS}. Yamazaki \cite{Y95} obtained some results for $s \geq
3$.
\end{problem}

\begin{problem} The fact that the multiplicities of the eigenvalues of a distance-regular graph are positive integers seems to be
one of the strongest known conditions for its intersection array. They are however expensive to compute.
Find necessary but easy to compute properties of the intersection numbers of distance-regular graphs that follow from the integrality of the multiplicities, such as the fact that for all prime numbers $p$ the number of
closed walks of length $p$ is divisible by $p$.
See Section \ref{sec:integralmultiplicities}.
\end{problem}

\begin{problem}
Bang \cite{Bang2014} showed that for $g\equiv 3 ~(\text{mod}~ 4)$ and $g=5$, there exists a positive $\epsilon_g$ such that if $\G$ is a triangle-free distance-regular graph with girth $g$ and large enough valency $k$,
then the smallest eigenvalue of $\Gamma$ is at least $(\epsilon_g -1)k$.
Show the same result for distance-regular graphs with odd girth. For non-bipartite distance-regular graphs with even
girth $g$  we can only expect that the smallest eigenvalue is at least $-k + C_g$ for a positive constant $C_g$, as the
folded $(2m+1)$-cube has smallest eigenvalue $-2m+1=-k+2$ and the Odd graph with valency $k$ has smallest eigenvalue $-k+1$.
\end{problem}

\begin{problem}
Show that for large enough $k$, the second largest eigenvalue of a
distance-regular graph with valency $k$ is at most $k-1$, as
conjectured by Koolen (unpublished). This would be best possible as
the Doubled Odd graphs have second largest eigenvalue $k-1$. For
distance-regular graphs with girth $6$, it was shown by Bang,
Koolen, and Park \cite{BKP2014pre}.
\end{problem}

\begin{problem}
\begin{enumerate}[(i)]
\item Determine the vertex-transitive distance-regular graphs.
\item Determine the distance-regular Cayley graphs.
\item Determine the arc-transitive distance-regular graphs.
\end{enumerate}
\noindent
See, e.g., \cite{ADJ15, Ma1994DCC,MP2003EJC,MP2007JCTB,MS2014JCTB}
for some results on distance-regular Cayley graphs.
\end{problem}

\begin{problem} Classify the distance-regular graphs with chromatic number $3$
and $a_1=1$. See Section \ref{sec:chromatic}.\end{problem}

We finish with a problem that is dual to Problem
\ref{problem:primalof} and that is relevant for the dual of Problem
\ref{problem:3}.

\begin{problem}\label{problem:dualof}
Show that there exists a constant $C$ such that for every primitive
cometric association scheme there exists an adjacency matrix, say,
$A_1$, such that $|\{j:p_{1j}^i\ne 0\}|\leq C$ for all $i$.
\end{problem}
