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

Is every distance-regular graph vertex-transitive?

share|improve this question
    
I added two tags. –  Felix Goldberg Sep 7 '12 at 11:28
1  
While, as pointed out in answers, the answer is "no", there is a conjecture that every distance-regular graph of sufficiently large diameter is not only vertex-transitive, but even distance-transitive. –  Dima Pasechnik Sep 8 '12 at 4:11
    
oops, sorry, forgot that this actually is disproved by examples of "quadratic forms" graphs. Still, they are vertex-transitive, so in this weaker form the conjecture still is open. –  Dima Pasechnik Sep 8 '12 at 4:14

5 Answers 5

up vote 13 down vote accepted

I don't think so. There are examples of even strongly regular graphs with a trivial automorphism group. See a detailed discussion here.

share|improve this answer
5  
I'm upvoting this answer because it's the only one to date emphasizing that the true answer is almost certainly exactly the opposite of the question. Most graphs have trivial automorphism group. Most regular graphs have trivial automorphism group. Most strongly regular graphs (almost certainly) have trivial automorphism group. There are a handful of situations where a very very strong combinatorial regularity property can only arise from the existence of a large group, but they are very much the exception. –  Gordon Royle Sep 7 '12 at 13:49

Here is a counterexample - Tutte 12 cage.

According to Wolfram alpha it is distance-regular yet not vertex-transitive.

Sage 5.2 confirms it is not vertex transitive and distance-regular.

Added Computer search with sage/networkx using graph enumeration didn't find small counterexamples

share|improve this answer
2  
Wooohoooo !! And somebody actually used the Tutte12Cage graph constructor :-D –  Nathann Cohen Sep 7 '12 at 12:56
    
@Nathan glad to learn it is in sage. The first time I constructed it from my database of named graphs. It is the same as sage's :-) –  joro Sep 7 '12 at 13:16

Here's a quasi-proof that the answer is no. Wikipedia says that Moore graphs are examples of distance regular graphs. It also says "It is not known whether a Moore graph with girth 5 and degree 57 exists, but Higman proved that it cannot be vertex-transitive, unlike the known ones." Or were you asking the question in the hope of a cheap answer to this open problem?

share|improve this answer
    
Moore graphs are some very special examples of distance-regular graphs. There are in fact abundant families of distance-regular graphs around, e.g. the hypercubes are distance-regular. –  Dima Pasechnik Sep 8 '12 at 4:16
    
Yes, but the hypercubes are vertex transitive, as are most of the obvious families. –  gowers Sep 8 '12 at 9:40

Very small examples of distance-regular graphs that are not vertex-transitive are the Chang graphs on 28 vertices. They are strongly regular but not vertex-transitive. They are constructed from the very symmetric graph T(8). The groups have sizes

http://en.wikipedia.org/wiki/Chang_graphs http://www.win.tue.nl/~aeb/graphs/Chang.html

384,360 and 96, which is not even divisibly by 28.

It is not true either that for large diameter, they have to be vertex-transitive. In 2005, Koolen and van Dam constructed new distance-regular graphs of arbitrary diameter d, by twisting the very symmetric Grassmann graphs (hence the name "twisted Grassmann graph"). They have two orbits on vertices.

share|improve this answer

In my answer to this question I commented that in the diameter 2 case it may be that most distance regular graphs have no automorphisms.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.