Count of maximal sextic toroidal graphs

Question

EDIT: Lots of pictures at Sextic Toroidal Graphs

There is one graph on 7 vertices, $K_7$, which is a maximal sextic toroidal graph (genus 1). It can be drawn on a torus with no edges crossing and all faces triangular. Map Coloring on a Torus made the first image. Embeddings of Graphs in a Torus made the second image.

The count of maximal sextic toroidal graphs is sequence A129033. $(1, 1, 2, 1, 1, 4, 2, 2, 4, 5, 2, ...)$. That matches surftri counts, also mentioned at Generating Triangulations.

$K_7$ a toroidal grid another way. The grid has a signature of $(1,1,1)$. This is the number of lines in each parallel class. Also the $7_{1,2,3}$ circulant graph.

The 16-cell graph is a triangular grid graph. The grid has a signature of $(1,1,2)$. Also the $8_{1,2,3}$ circulant graph.

The {"CompleteTripartite", {3, 3, 3}} graph is a triangular grid graph. The grid has a signature of $(3,3,3)$. Also the $9_{1,2,4}$ circulant graph.

The {"Circulant", {9, {1, 2, 3}}} graph is a triangular grid graph. The grid has a signature of $(1,1,3)$.

Here are the graphs for 10 and 11 vertices.

All of the grids so far have been circulant graphs, which suggests a construction method for these triangular grids.

Not all triangular grid graphs are circulant, with the Shrikhande graph being one example. A notation that handles both circulant and Shrikhande is needed.

Here's a grid of $V$, A129033, and inequivalent circulant graphs which are local hexagons. The toroidal sextics will be a subsets of circulants and Shrikhande-like examples.

How does sequence A129033. $(1, 1, 2, 1, 1, 4, 2, 2, 4, 5, 2, ...)$ continue for $18 - 25$ vertices?

Answer 1

If we have a toroidal embedding of such a graph $G$, deleting any vertex $v$ produces a hexagonal face, which is a $6$-cycle $C(v)$ through $v$'s $6$ neighbors. Determining $C(v)$ for every vertex $v$ gives enough information to reconstruct the embedding: the faces containing $v$ are precisely the triangles $uvw$ where $uw$ is an edge of $C(v)$. So we can try to find an embedding by picking $C(v)$ for each $v$.

These have to be consistent: if $uw$ is an edge of $C(v)$, then $vw$ must be an edge of $C(u)$ and $uv$ must be an edge of $C(w)$. Moreover, every edge $xy$ of $G$ has to appear in exactly $2$ of these $6$-cycles: if $xy$ is the edge between triangles $vxy$ and $wxy$, it appears in $C(v)$ and $C(w)$ only. Once that's satisfied, we've embedded $G$ on a surface of genus $0$...

...which means that a final check we have to do is whether we've embedded $G$ on a torus or on a Klein bottle. (At this point, we have the faces, so all we have to do is try to orient them: give each triangle a clockwise or counterclockwise orientation so that each edge is traversed in opposite directions by its two triangles. This is possible on the torus, but not on the Klein bottle.)

For example, here is why $9_1$ is not toroidal. If we look at the subgraphs induced by the neighbors of each of the $9$ vertices, we get the $9$ graphs below:

The neighborhoods of vertices $3, 4, 5, 6, 7$ all have the same shape, with edges $12$ and $89$ on the sides. For each of those graphs, edges $12$ and $89$ have to appear in a $6$-cycle through the neighbors: for example, in the neighborhood of $3$, either we use the edge $12$ or we'd have to pick $14, 15, 24, 25$ (since those are the only other neighbors of $1$ and $2$), which would create a $4$-cycle. This does not produce an embedding, since the edges $12$ and $89$ appear in too many faces.

$9_2$ doesn't produce similar contradictions; by hand, I've managed to find an embedding (the process is similar to solving a Sudoku puzzle) but it turned out to be non-orientable. I made a couple of arbitrary choices along the way, so it's possible that a toroidal embedding of $9_2$ exists; this process really ought to be done by computer (and shouldn't be too hard to code up).

Answer 2

Equivelar maps on the torus by Ulrich Brehm and Wolfgang Kuhnel has an exact formula.

Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds by Thom Sulanke and Frank H. Lutz has the actual sequence up to 100. A129033.

$(1, 1, 2, 1, 1, 4, 2, 2, 4, 5, 2, 5, 3, 6, 6, 4, 3, 11, 5, 5, 7, 9, 4, 11, 5, 11, 8, 7, 8, 16, 6, 8, 10, 16, 6, 15, 7, 13, 14, 10, 7, 24, 10, 14, 12, 16, 8, 19, 12, 21, 14, 13, 9, 30, 10, 14, 19, 23, 14, 23, 11, 20, 16, 23, 11, 36, 12, 17, 22, 23, 16, 27, 13, 34, 21, 19, 13, 40, 18, 20, 20, 31, 14, 39, 20, 27, 22, 22, 20, 47, 16, 27, 27, 37)$