The orientable genus of some joins of complete graphs with large edgeless graphs

In an earlier paper the authors showed that with one exception the nonorientable genus of the graph Km¯+Kn with m≥n−1m≥n−1, the join of a complete graph with a large edgeless graph, is the same as the nonorientable genus of the spanning subgraph Km¯+Kn¯=Km,n. The orientable genus problem for Km¯+Kn with m≥n−1m≥n−1 seems to be more difficult, but in this paper we find the orientable genus of some of these graphs. In particular, we determine the genus of Km¯+Kn when nn is even and m≥nm≥n, the genus of Km¯+Kn when n=2p+2n=2p+2 for p≥3p≥3 and m≥n−1m≥n−1, and the genus of Km¯+Kn when n=2p+1n=2p+1 for p≥3p≥3 and m≥n+1m≥n+1. In all of these cases the genus is the same as the genus of Km,nKm,n, namely ⌈(m−2)(n−2)/4⌉⌈(m−2)(n−2)/4⌉.