Nonorientable genus of nearly complete bipartite graphs

LetG(m, n, k), m, n≥3,k≤min(m, n), be the graph obtained from the complete bipartite graphK _m,n by deleting an arbitrary set ofk independent edges, and let $$f(m,n,k) = [(m - 2)(n - 2) - k]/2.$$ It is shown that the nonorientable genus (tilde gamma ) (G(m, n, k)) of the graphG(m, n, k) is equal to the upper integer part off(m, n, k), except in trivial cases wheref(m, n, k)≤0 and possibly in some extreme cases, the graphsG(k, k, k) andG(k + 1,k, k). These cases are also discussed, obtaining some positive and some negative results. In particular, it is shown thatG(5, 4, 4) andG(5, 5, 5) have no nonorientable quadrilateral embedding.