Settling the nonorientable genus of the nearly complete bipartite graphs

2023/05/23 by Singh, Warren, Sun, Timothy
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2305.14048

Abstract

A graph is said to be nearly complete bipartite if it can be obtained by deleting a set of independent edges from a complete bipartite graph. The nonorientable genus of such graphs is known except in a few cases where the sizes of the partite classes differ by at most one, and a maximum matching is deleted. We resolve these missing cases using three classic tools for constructing genus embeddings of the complete bipartite graphs: current graphs, diamond sums, and the direct rotation systems of Ringel.

Related

• Constructing nonorientable genus embedding of complete bipartite graph minus a matching
• Jungerman ladders and index 2 constructions for genus embeddings of dense regular graphs
• Determination of the 4-genus of a complete graph (with an appendix)
• Face distributions of embeddings of complete graphs
• Spectral characterizations of two families of nearly complete bipartite graphs