Biembeddings of Archdeacon type: their full automorphism group and their number

Abstract

Archdeacon, in his seminal paper $[1]$, defined the concept of Heffter array in order to provide explicit constructions of ${\mathbb{Z}}_v$-regular biembeddings of complete graphs $K_v$ into orientable surfaces. In this paper, we first introduce the quasi-Heffter arrays as a generalization of the concept of Heffer array and we show that, in this context, we can define a $2$-colorable embedding of Archdeacon type of the complete multipartite graph $K_{\frac{v}{t}\times t}$ into an orientable surface. Then, our main goal is to study the full automorphism groups of these embeddings: here we are able to prove, using a probabilistic approach, that, almost always, this group is exactly ${\mathbb{Z}}_v$. As an application of this result, given a positive integer $t\not\equiv 0(\mathrm{mod}4)$, we prove that there are, for infinitely many pairs of $v$ and $k$, at least $(1-o(1))\frac{(\frac{v-t}{2})!}{\varphi (v)}$ non-isomorphic biembeddings of $K_{\frac{v}{t}\times t}$ whose face lengths are multiples of $k$. Here $\varphi (\cdot )$ denotes the Euler's totient function. Moreover, in case $t=1$ and $v$ is a prime, almost all these embeddings define faces that are all of the same length $kv$, i.e. we have a more than exponential number of non-isomorphic $kv$-gonal biembeddings of $K_v$.