Count of maximal sextic toroidal graphs

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:

neighborhoods

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).


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)$