A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ neighbours of $y$ in $G_{i-1}(x)$ and $b_i$ neighbours of $y$ in $G_{i+1}(x)$, where $G_i(x)$ is the set of vertices $y$ of $G$ with $d(x,y)=i$. Here $d(x,y)$ is the distance between $x$ and $y$, and $D$ is the diameter.
My question is: given a graph $G$ with $n$ vertices and $m$ edges, how quickly can we test if $G$ is distance-regular?
Clearly it can be done in $O(nm)$ time, since in that amount of time we can find the distance partition from each vertex using breadth-first search and count edges between the different cells. Probably we can also do it by matrix multiplication in $O(Dn^\alpha)$ where $\alpha$ is the exponent for matrix multiplication (I didn't work out the details).
Can it be done quicker?
