# Which graphs embedded in surfaces have symmetries acting transitively on vertex-edge flags?

A vertex-edge flag in a graph is a vertex together with an edge incident to that vertex. Given a graph $\Gamma$ embedded in a compact oriented surface $S$, when does the group of homeomorphisms of $S$ act transitively on vertex-edge flags of $\Gamma$?

We can start by looking a graphs embedded in the sphere, and start among those by looking at graphs that consist of the vertices and edges of a convex polyhedron. Among these, the obvious examples on which isometries act transitively on vertex-edge flags are the 5 Platonic solids. However, there are also two Archimedean solids with this property, namely the cuboctahedron:

and the icosidodecahedron:

I believe these are all the convex polyhedra on which isometries act transitively on vertex-edge flags. A polyhedron is said to be isotoxal if isometries act transitively on edges. There are 9 isotoxal convex polyhedra, and among these I see 7 on which isometries act transtively on vertex-edge flags: the 5 Platonic solids and the 2 shown above.

There are also infinitely many other connected graphs embedded in the sphere on which isometries act transitively on vertex-edge flags, namely the hosohedra, like this:

and the dihedra, like this:

I believe these are all the connected graphs embedded in the sphere on which isometries acts transitively on vertex-edge flags. If we consider graphs embedded in the sphere that are not connected, we get a host of other examples: for example, a bunch of equal-sized regular $n$-gons embedded in the sphere. If we further drop the requirement that the homeomorphisms be isometries, we get even more examples: for example, a bunch of copies of the complete graph on 4 vertices embedded in the sphere. I am happy to restrict attention to connected graphs, to avoid such clutter.

I am also happy to omit graphs that have self-loops.

So, here is a sub-question that interests me: what are all the connected graphs without self-loops embedded in the sphere on which homeomorphisms of the sphere act transitively on vertex-edge flags? Have I listed them all, or are there more?

(Whoops, here are some more: the empty graph, the graph with one vertex and no edges, and the graph with two vertices and one edge connecting them. The last might be considered a degenerate hosohedron.)

When we go to higher genus the situation becomes a lot more complicated and interesting. For example, in genus 3 we have Klein's quartic curve tiled by 56 triangles meeting 7 at each vertex:

So, I'd be perfectly happy to hear classifications that only handle surfaces of genus less than some fixed value.

• A very common term for a vertex-edge flag is an arc. Let me use this for simplicity. You are asking about maps with an arc-transitive group of automorphisms. It's not hard to see that the maximal amount of symmetry a map can have is to be arc-transitive with the arc-stabiliser having order $2$. This is the so-called "regular" case that Noam mentioned. In that case, the vertex-stabiliser is dihedral, of order $2k$, where $k$ is the valency. – verret Apr 29 '16 at 20:42
• The only other option is that the arc-stabiliser is trivial and hence the group acts regularly on arcs. In that case, the vertex-stabiliser acts regularly on the neighbours, so it must be either cyclic of order $k$, or dihedral of order $k$ (in which case $k$ is even). These are all quite well studied objects, although not as much as the regular ones. In particular, they can be defined group-theoretically and, using this, can be enumerated up to a few thousand vertices and quite high genus, 100 say. (See math.auckland.ac.nz/~conder for example) – verret Apr 29 '16 at 20:42
• Isn't the vertex-edge flag graph somehow related to the line digraph? – draks ... May 16 '17 at 15:23

A (connected) map $M$ is regular if its automorphism group acts transitively (and hence regularly) on the set of flags. On the other hand, the definition of "symmetry" you're using in the question is weaker than the standard definition of map automorphism, which in the case of maps embedded on compact oriented surfaces would restrict to orientation-preserving homeomorphisms (that also preserve the graph incidence relationships). This stronger definition rules out the cuboctahedron and icosidodecahedron, and indeed Siran asserts that the only regular maps on the sphere are the five platonic solids, the hosohedra ("$k$-dipoles") and the dihedra ("$k$-cycles") (plus the "semi-stars", if you allow graphs with dangling semi-edges).
• @JohnBaez Glad you found it useful! On v-e-f flags vs v-e flags, Siran's definition of regular map allows for nonorientable regular maps, but in the oriented case it seems natural to me to define regular maps as combinatorial maps $M = (D,v,e)$ such that $Aut(M)$ (respectively $Mon(M) = \langle v,e\rangle$) acts transitively (respectively, freely) on the set of darts $D$. Note that a dart is essentially the same thing as a v-e flag, except in the case of loops. I see that this definition of "oriented regular map" is considered by Roman Nedela here: savbb.sk/~nedela/CMbook.pdf. – Noam Zeilberger May 2 '16 at 9:56