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.

• Your right that we can generalize the definition of complete regularity to non-planar graphs. It doesn't require a notion of "duality" however. Essentially complete regularity means a (graph) automorphism is available that swaps any two specified vertices. Aug 20, 2017 at 13:46
• I must admit, I find it hard to understand these kinds of definitions. What you said sounds like the definition of a vertex-transitive graph. Here is MathWorld: every pair of vertices is equivalent under some element of its automorphism group. Aug 20, 2017 at 13:56
• Yes, that is so. To say a graph is regular says only that all vertices have equal degrees, and since graph automorphisms preserve adjacency, vertex transitivity implies regularity but is not equivalent to that (vertex transitivity is a stronger condition). The Wikipedia article on regular graphs points out some additional properties, like strongly regular, which is a condition of intermediate "strength". Aug 20, 2017 at 14:10
• omeyer.gmxhome.de/On_Completely_Regular.pdf has some interesting ideas. In particular I think the complete graph $K_5$ is being identified as completely regular through embedding on a torus, rather than in the plane. Aug 20, 2017 at 14:11
• Thank you, @user399601! I'll look into this. @hardmath: Are you saying that complete regularity is the same as vertex-transitivity? In that case, you are giving the words a different sense than me. There are many vertex-transitive graphs that are not completely regular (that is, that does not have regular duals). Aug 20, 2017 at 14:24

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.