ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.02
https://doi.org/10.26493/1855-3974.2910.5b3
(Also available at http://amc-journal.eu)
On the number of non-isomorphic (simple)
k-gonal biembeddings of complete multipartite
graphs*
Simone Costa † , Anita Pasotti
DICATAM, Università degli Studi di Brescia, Via Branze 43, 25123 Brescia, Italy
Received 21 June 2022, accepted 16 October 2023, published online 23 September 2024
Abstract
This article aims to provide exponential lower bounds on the number of non-isomorphic
k-gonal face-2-colourable embeddings (sometimes called, with abuse of notation, biem-
beddings) 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 Yazıcı in 2020, we obtain that, for infinitely many values of k and v, there
are at least k
k
2+o(k) ·2v·
H(1/4)
(2k)2
+o(v) non-isomorphic k-gonal face-2-colourable embeddings
of Kv , where H(·) is the binary entropy. Moreover about the embeddings of K vt ×t, for
t ∈ {1, 2, k}, we provide a construction of 2v·
H(1/4)
2k(k−1)+o(v,k) non-isomorphic k-gonal face-
2-colourable embeddings whenever k is odd and v belongs to a wide infinite family of
values.
Keywords: Topological embedding, non-isomorphic embedding, Heffter array.
Math. Subj. Class. (2020): 05C10, 05C15, 05B20, 54C25
*The authors were partially supported by INdAM–GNSAGA.
†Corresponding author.
E-mail addresses: simone.costa@unibs.it (Simone Costa), anita.pasotti@unibs.it (Anita Pasotti)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.02
https://doi.org/10.26493/1855-3974.2910.5b3
(Dostopno tudi na http://amc-journal.eu)
O številu neizomorfnih (enostavnih) k-gonskih
bivložitev polnih večdelnih grafov*
Simone Costa † , Anita Pasotti
DICATAM, Università degli Studi di Brescia, Via Branze 43, 25123 Brescia, Italy
Prejeto 21. junija 2022, sprejeto 16. oktobra 2023, objavljeno na spletu 23. septembra 2024
Povzetek
Namen tega članka je podati eksponentne spodnje meje za število neizomorfnih k-
gonskih vložitev z 2-barvnimi lici (te vložitve včasih, ne najbolj posrečeno, imenujejo
bivložitve) polnega večdelnega grafa na orientabilne ploskve.
V ta namen uporabimo koncept, ki ga je leta 2015 predstavil Archdeacon, in sicer
Heffterjevo matriko in njene povezave z vložitvami grafov. Pokažemo, da – ob določenih
predpostavkah – iz ene same Heffterjeve matrike dobimo eksponentno število različnih
vložitev grafov. Če izkoristimo to idejo, lahko – izhajajoč iz tabel, ki so jih konstruirali
Cavenagh, Donovan in Yazıcı leta 2020 – pokažemo, da za neskončno mnogo vrednosti
k in v obstaja najmanj k
k
2+o(k) · 2v·
H(1/4)
(2k)2
+o(v) neizomorfnih k-gonskih vložitev polnega
grafa Kv z 2-barvnimi lici, kjer je H(·) binarna entropija. Poleg tega za vložitve K vt ×t, za
t ∈ {1, 2, k}, predstavimo konstrukcijo 2v·
H(1/4)
2k(k−1)+o(v,k) neizomorfnih k-gonskih vložitev
z 2-barvnimi lici, kadarkoli je k lih, v pa pripada široki neskončni družini vrednosti.
Ključne besede: Topološka vložitev, neizomorfna vložitev, Heffterjeva matrika.
Math. Subj. Class. (2020): 05C10, 05C15, 05B20, 54C25
*Avtorji so bili delno podprti s strani INdAM–GNSAGA.
†Kontaktni avtor.
E-poštna naslova: simone.costa@unibs.it (Simone Costa), anita.pasotti@unibs.it (Anita Pasotti)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/