Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Aaron Meyerowitz May 1 '13 at 8:30
    
This might be helpful: networkx.lanl.gov/trac/ticket/536 –  Tony Huynh May 1 '13 at 8:42
    
@Tony: Thanks. They compute the matrix of distances then apply the definition of distance regularity to that, taking at least $n^3$ time. –  Brendan McKay May 1 '13 at 12:30
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.