An optimal construction for complete graph embeddings with duals of low connectivity

2024/10/03 by Sun, Timothy
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2410.02124

Abstract

We describe a construction for embeddings of complete graphs where the dual has a cutvertex and the genus is close to the minimum genus of the primal graph. When the number of vertices is congruent to 5 modulo 12, we further guarantee that the dual is simple and that the genera of the resulting embeddings match a lower bound of Brinkmann, Noguchi, and Van den Camp, showing that their lower bound is tight infinitely often.

Related

• Face distributions of embeddings of complete graphs
• Lower bound on the number of the maximum genus embedding of K_n,n
• Jungerman ladders and index 2 constructions for genus embeddings of dense regular graphs
• Genus embeddings of complete graphs minus a matching
• Maximum genus embeddings of dense eulerian graphs with specified faces