The nonorientable genus of joins of complete graphs with large edgeless graphs

We show that for n = 4 and n >= 6, K, has a nonorientable embedding in which all the facial walks are hamilton cycles. Moreover, when n is odd there is such an embedding that is 2-face-colorable. Using these results we consider the join of an edgeless graph with a complete graph, (K) over bar (m) + K-n = Km+n - K-m, and show that for n >=, 3 and m >= n - I its nonorientable genus is [(m, - 2)(n - 2)/2] except when (in, n) = (4, 5). We then extend these results to find the nonorientable genus of all graphs K, + G where m V (G) I - 1. We provide a result that applies in some cases with smaller m when G is disconnected. (c) 2007 Elsevier Inc. All rights reserved.