On the number of non-isomorphic (simple) $k$-gonal biembeddings of complete multipartite graphs

Simone Costa, Anita Pasotti

Published 2021-11-16, updated 2022-03-02Version 2

This article aims to provide exponential lower bounds on the number of non-isomorphic $k$-gonal biembeddings of the complete multipartite graph into orientable surfaces. For this purpose, we use the concept, introduced by Archdeacon in 2015, of Heffer array and its relations with graph embeddings. In particular we show that, under certain hypotheses, from a single Heffter array, we can obtain an exponential number of distinct graph embeddings. Exploiting this idea starting from the arrays constructed by Cavenagh, Donovan and Yazici in 2020, we obtain that, for infinitely many values of $k$ and $v$, there are at least $k^{\frac{k}{2}+o(k)} \cdot 2^{v\cdot \frac{H(1/4)}{(2k)^2}+o(v)}$ non-isomorphic $k$-gonal biembeddings of $K_v$, where $H(\cdot)$ is the binary entropy. Moreover about the embeddings of $K_{\frac{v}{t}\times t}$, for $t\in\{1,2,k\}$, we provide a construction of $2^{v\cdot \frac{H(1/4)}{2k(k-1)}+o(v,k)}$ non-isomorphic $k$-gonal biembeddings whenever $k$ is odd and $v$ belongs to a wide infinite family of values.