Welcome to MathOverflow

Question

3

Is every distance-regular graph vertex-transitive?

edited Sep 7 at 11:28

Felix Goldberg
2,385●4●12

asked Sep 7 at 10:19

Agelos
83●4

I added two tags. – Felix Goldberg Sep 7 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 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 at 4:14

Felix Goldberg · Accepted Answer · 2012-09-07 11:26:56Z UTC

11

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 at 11:26

Felix Goldberg
2,385●4●12

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 at 13:49

joro · Answer 2 · 2012-09-08 10:08:01Z UTC

13

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

edited Sep 8 at 10:08

answered Sep 7 at 11:52

joro
4,270●1●10●31

2

Wooohoooo !! And somebody actually used the Tutte12Cage graph constructor :-D – Nathann Cohen Sep 7 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 at 13:16

gowers · Answer 3 · 2012-09-07 11:27:13Z UTC

3

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?

answered Sep 7 at 11:27

gowers
17.8k●9●77●130

	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 at 4:16
	Yes, but the hypercubes are vertex transitive, as are most of the obvious families. – gowers Sep 8 at 9:40

Frédéric · Answer 4 · 2012-12-06 09:45:56Z UTC

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.

Aaron Meyerowitz · Answer 5 · 2012-12-06 10:33:40Z UTC

0

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 at 10:33

Aaron Meyerowitz
11.6k●1●10●31

Is every distance-regular graph vertex-transitive?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

5 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.