7
$\begingroup$

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?

$\endgroup$
3
  • $\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$ May 1, 2013 at 8:30
  • $\begingroup$ This might be helpful: networkx.lanl.gov/trac/ticket/536 $\endgroup$
    – Tony Huynh
    May 1, 2013 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$ May 1, 2013 at 12:30

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.