Nonorientable genus of nearly complete bipartite graphs (Q1092915)

The graph obtained by deleting k independent edges from the complete bipartite graph \(K_{m,n}\) is denoted by G(m,n,k). Set \(f(m,n,k)=((m- 2)(n-2)-k)/2\). The lower bound \({\tilde \gamma}\)(G(m,n,k))\(\geq \lceil f(m,n,k)\rceil\) is readily obtained. Using surgical imbedding techniques, the author shows that the lower bound is attained - except in trivial cases where F(m,n,k)\(\leq 0\) and possibly in the extreme cases \(G(k+1,k,k)\) with k even and G(k,k,k) with \(k=5\) (the graph is planar) or not divisible by 4. Strict inequality may hold, as \({\tilde \gamma}\)(G(5,4,4))\(=2\) and \({\tilde \gamma}\)(G(5,5,5))\(=3\).