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?

  • $\begingroup$ That's fairly quick... A distance regular graph, of course, need not be distance transitive. But many are. How quickly can we decide if a graph is distance transitive? It is not obvious that either bounds the other, but it would be interesting if the two differed. $\endgroup$ – Aaron Meyerowitz May 1 '13 at 8:30
  • $\begingroup$ This might be helpful: networkx.lanl.gov/trac/ticket/536 $\endgroup$ – Tony Huynh May 1 '13 at 8:42
  • 1
    $\begingroup$ @Tony: Thanks. They compute the matrix of distances then apply the definition of distance regularity to that, taking at least $n^3$ time. $\endgroup$ – Brendan McKay May 1 '13 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.