Is every distance-regular graph vertex-transitive?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ I added two tags. $\endgroup$– Felix GoldbergCommented Sep 7, 2012 at 11:28
-
2$\begingroup$ 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. $\endgroup$– Dima PasechnikCommented Sep 8, 2012 at 4:11
-
$\begingroup$ 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. $\endgroup$– Dima PasechnikCommented Sep 8, 2012 at 4:14
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
1
I don't think so. There are examples of even strongly regular graphs with a trivial automorphism group. See a detailed discussion here.
answered Sep 7, 2012 at 11:26
-
5$\begingroup$ 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. $\endgroup$ Commented Sep 7, 2012 at 13:49
$\begingroup$
$\endgroup$
2
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
-
2$\begingroup$ Wooohoooo !! And somebody actually used the Tutte12Cage graph constructor :-D $\endgroup$ Commented Sep 7, 2012 at 12:56
-
$\begingroup$ @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 :-) $\endgroup$– joroCommented Sep 7, 2012 at 13:16
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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?
-
1$\begingroup$ 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. $\endgroup$ Commented Sep 8, 2012 at 4:16
-
$\begingroup$ Yes, but the hypercubes are vertex transitive, as are most of the obvious families. $\endgroup$– gowersCommented Sep 8, 2012 at 9:40
$\begingroup$
$\endgroup$
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.
answered Dec 6, 2012 at 10:33