Nonorientable genus embedding of nearly complete bipartite graphs

Abstract

The nearly complete bipartite graph $G(m,n,k)$ is obtained by removing $k$ independent edges from the complete bipartite graph $K_{m,n}$. In this paper, we prove that for any nearly complete bipartite graph $G(m,n,k)$ with $m,n\ge 3$, and $(m,n,k)\notin \{(5,4,4)$, $(4,5,4)$, $(5,5,5)\}$, there exists a nonorientable genus embedding $\hat{I}$ satisfying ${\tilde{\hat{I}}}^3(\hat{I})=\max \{\lceil ((m-2)(n-2)-k)/2\rceil ,1\}$. This embedding can be constructed by starting from an embedding of some $G(p,q,h)$ with $h\le 6$ and $p,q\le 7$, and then iteratively adding multiple copies of $G(2,2,2)$, $G(2,0,0)$ and $G(0,2,0)$. As a consequence, the previously unresolved nonorientable genus ${\tilde{\hat{I}}}^3(G(n+1,n,n))$ for even $n$ and ${\tilde{\hat{I}}}^3(G(n,n,n))$ for arbitrary $n$ are now determined.