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

preprint2022arXivOpen access

Abstract

This article aims to provide exponential lower bounds on the number of non-isomorphic kk-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 kk and vv, there are at least kk2+o(k)⋅2v⋅H(1/4)(2k)2+o(v)k^{\frac{k}{2}+o(k)} \cdot 2^{v\cdot \frac{H(1/4)}{(2k)^2}+o(v)} non-isomorphic kk-gonal biembeddings of KvK_v, where H(⋅)H(\cdot) is the binary entropy. Moreover about the embeddings of Kvt×tK_{\frac{v}{t}\times t}, for t∈{1,2,k}t\in\{1,2,k\}, we provide a construction of 2v⋅H(1/4)2k(k−1)+o(v,k)2^{v\cdot \frac{H(1/4)}{2k(k-1)}+o(v,k)} non-isomorphic kk-gonal biembeddings whenever kk is odd and vv belongs to a wide infinite family of values.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.