Graph theory: Relation between complete regularity and distance-transitivity MathWorld defines complete regularity only for polyhedral graphs, so the Platonic graphs are the only completely regular graphs. But, given a suitable definition of duality that extends that notion to (some) nonplanar graphs, we should be able to say that, for example, K₅ is also completely regular. What I’m wondering is this: Is a graph’s being completely regular in this extended sense equivalent to its being distance-transitive?
Appendix on why I’m asking:
I’m nothing like a mathematician, and I don’t have a good understanding of graph theory, but I find it fascinating and want to understand more. This particular question came up as I was thinking about ways to remove the edges and corners from Go (Baduk/Weiqi). At first I thought all 4-regular graphs would do the trick, but some such graphs still have something like corners. An example is playing on the squares of a Rubik’s cube, where some squares are easier to surround with a chain of connected stones. I learned that this feeling that «not all vertices are equal» was due to the fact that the Rubik’s cube graph (not the «skeleton», but the result of making adjacent squares into adjacent vertices) is not vertex-transitive. Looking into graphs that are vertex-transitive I realized that there is a sort of hierarchy of uniformness. Some graphs are also edge-transitive. But some graphs are intuitively even more uniform than the ones that are both vertex- and edge-transitive. 4-regular examples are the octahedral graph, K₅ and the torus grid graph. My informal understanding of the property I’m looking for is that all the faces of the graph has the same number of sides. This can be made precise in the case of the octahedral graph: its dual is also regular. It seemed to be the right property, but I thought only planar graphs had duals, so I looked further, and it seemed that all distance-transitive graphs looked like the ones I intuitively understood as the «most» uniform. So when I learned that one could give a sense to the notion of the dual (not sure about the «the») of a non-planar graph, I had to wonder: what is the relation between these two properties? The one (complete regularity) seems to fit my intuition, but no one uses the term in this extended sense, and the other (distance-transitivity) is quite opaque to me. I don’t know if it is an accident that the graphs that have «faces with the same number of sides» are distance-transitive. When I'm talking about "faces" I'm imagining the graph on a surface on which its crossing number is 0.
It was this forum post that first lit my curiosity.
 A: First, I do not think that "completely regular", as defined by Mathworld, is a standard term in Graph Theory. (It is used in connection with distance-regular graphs, but with a completely different meaning.)
Second, their definition has nothing to do with automorphisms. They state that a graph is regular if all vertices have the same degree, and that a polyhedral graoh is "completely regular" if the graph is regular and its dual is regular.
Third, since there are (many) diatance-regular graphs with no non-identity automorphisms, it is going to be very difficult to come up with a set of useful regularity conditions that imply a graph is distance-transitive. (I am excluding statements such as "cubic girth five diameter two on 10 vertices".)
Finally the polyhedral case (planar, 3-connected) is a poor guide to what goes on in general. It might be worth noting that there are "regular" polytopes (120-cell, 600-cell) in $\mathbb{R}^4$ that are
very symmetric but not distance-transitive. Note also that here "regular" means transitive on flags, and is a very strong condition.
