/^creative ^commor ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 17 (2019) 223-253 https://doi.org/10.26493/1855-3974.1695.144 (Also available at http://amc-journal.eu) The orientable genus of the join of a cycle and a complete graph Dengju Ma * School of Sciences, Nantong University, 226019, Nantong, China Han Ren t Department of Mathematics, East China Normal University, 200062, Shanghai, China Received 8 May 2018, accepted 22 April 2019, published online 2 October 2019 ARS MATHEMATICA CONTEMPORANEA Abstract Let m and n be two integers. In the paper we show that the orientable genus of the join of a cycle Cm and a complete graph Kn is [ (m-2Hn-2) ] if n = 4 and m > 12, or n > 5 and m > 6n — 13. Keywords: Surface, orientable genus of a graph, join of two graphs. Math. Subj. Class.: 05C10 1 Introduction Let G and H be two disjoint graphs. The join of G with H, denoted by G + H, is the graph obtained from the union of G and H by adding edges joining every vertex of G to every vertex of H. A cycle with m vertices is denoted by Cm, and a complete graph with n vertices denoted by Kn. Our investigation of the orientable genus of Cm + Kn is inspired by the problem of the critical graphs on surfaces. A graph G is k-critical if x(G) = k but x(G') < k for every proper subgraph of G, where x(H) denotes the chromatic number of a graph H. If Gi is k-critical and G2 is l-critical, it is known that G1 + G2 is (k + 1)-critical. Since an odd cycle is 3-critical and Kn is n-critical, the join of an odd cycle and Kn is (n + 3)-critical. Also, there are only finite many k-critical graphs on a surface if k > 7 ([4, 6, 7, 13]). So it is an interesting problem to explore the orientable genus of the join of an odd cycle (or a cycle) and Kn. * Corresponding author. Supported by NNSFC under the granted number 11171114. t Supported by NNSFC under the granted number 11171114, Science and Technology Commission of Shanghai Municipality under grant No. 13dz2260400. E-mail addresses: ma-dj@163.com (Dengju Ma), hren@math.ecnu.edu.cn (Han Ren) ©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/ 224 Ars Math. Contemp. 17 (2019) 223-253 Let us look back the history of studying the orientable genus of the join of two graphs. Let Kt be the compliment graph of Kt. The complete bipartite graph Km,n and Kn (n > 2) can be viewed as Km + Kn and K1 + Kn-1, respectively. It is cheerful that the orietable genera of Kn and Km,n have been determined ([10, 11]). Upon the orientable genus of Km + Kn there are some results. Craft [3] verified that Km + Kn has the same orientable genus as that of Km,n, when n is even and m > 2n - 4. Ellingham and Stephens [5] determined the orientable genus of Km + Kn if n is even and m > n, or n = 2p + 2 for p > 3 and m > n — 1, or n = 2p + 1 for p > 3 and m > n +1. Korzhik [8] contributed many results on the orientable genus of Km + Kn with m < n — 2. Let m > 3 and n > 1 be two integers. If n =1, then Cm + Kn is a planar graph. If n = 2, then Cm + Kn has a minor isomorphic to K5. So the orientable genus of Cm + K2 is at least one. Since Cm + K2 can be embedded on the torus, the orientable genus of Cm + K2 is one. If n = 3, then Kn is exactly the cycle C3. Craft [2] has proved that the orientable genus of Cm + C3 is [ m-2 ]. What is the orientable genus of Cm + Kn if n > 4? In the paper we shall show that the orientable genus of Cm + Kn is [ (m-2H"-2) ] if n = 4 and m > 12, or n > 5 and m > 6n — 13. Since Km,n is a spanning subgraph of Cm + Kn, a lower bound of the oreintable genus of Cm + Kn is that of Km,n, which is [ (m-2H"-2) ]. The key to determine the orientable genus of Cm + Kn is the construction of an embedding of Cm + Kn on the orientable surface of genus [ (m-2H"-2) ]. We mainly use two methods of adding tubes to construct an embedding of Cm + Kn. Our general strategy of constructing an embedding is as follows. First, we construct an embedding of a spanning subgraph of Cm + Kn which contains Cm, a spanning subgraph of Kn, and some edges between Cm and Kn on some orientable surface. Second, we apply the first method of adding tubes described in Section 2 to attach all the rest edges in Kn and some edges between Cm and Kn. Third, we apply the second method of adding tubes described in Section 2 to attach all the rest edges between Cm and K„. The remainder of the section is contributed for some terms. The other undefined terms can be found in [1, 9], or [14]. A surface is a compact connected 2-dimensional manifold without boundary. The orientable surface Sg (g > 0) can be obtained from a sphere with g handles attached, where g is called the genus of Sg. A graph G is able to embed in a surface S if it can be drawn in the surface such that any edge does not pass through any vertex and any two edges do not cross each other. The orientable genus of a connected graph G, denoted by 7(G), is the smallest nonnegative integer g such that G can be embedded in the orientable surface Sg. An embedding n of a connected graph in a surface S is called 2-cell embedding if any connected component of S — n, called a face, is homeomorphic to an open disc. In a 2-cell embedding of a connected graph G, the boundary of a face in n is a closed walk of G, which is called the facial walk. If a facial walk is a cycle, then it is called a facial cycle. Let v be a vertex of a graph G embedded on a surface. A local rotation nv at the vertex v is a cyclic permutation of the edges incident with v. Suppose that v is incident with edges vu1,vu2,..., vun in this order. Then nv can be written by u1; u2,..., un. Furthermore, if i1; i2,..., ik are k continuous numbers in {1,2,..., n}, where 2 < k < n, then we call uil, ui2,..., uik a segment of the local rotation at v. A graph H is a supergraph of G if G is a subgraph of H. If a cycle with n (> 3) vertices v1; v2,..., vn in this order, then it is written by v1v2... vnv1 and it is always oriented by this order. D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 225 2 Two methods of constructing embeddings Let D1 and D2 be two facial cycles of a 2-cell embedding on a surface S such that the orientation of D1 is the reverse of that of D2. By adding a tube T to the surface S between D1 and D2, we mean that we cut two holes A1 and A2 in S such that Ai is in the interior of Di and orient the boundary of Aj as that of Dj, then the tube T welds Ai with A 2 in such a way that the rim of one of the ends of T coincides with the boundary of A1 and the rim of the other end of T coincides with the boundary of A2. Lemma 2.1. Suppose that G is a graph which has a vertex subset {wo, zi,z2,...,zt}u{xj | i = 1, 2,. .., 2t} U {yj | j = 1, 2,. .., 4t}, where z1, z2,..., zt need not be different, and suppose that G contains no edges in the set E' = {w0xi | i = 1, 2,..., 2t} U {xiyj | i =1, 2,..., 2t; j = 1, 2,..., 4t} U ({xjXj+1,. .. ,XjX2t | i = 1, 2,. .., 2t - 1} \ {x2i-1x2i | i = 1, 2,. .. ,t}). Suppose that n is a 2-cell embedding of G on the orientable surface Sg with the following properties: (i) For i = 1, 2,... ,t, R0}i = w0y4i-3y4i-2w0 and R'0 j = w0y4i-1y4iw0 are facial cycles of n. (ii) For i = 1, 2,... ,t, Q0ji = zix2i-1x2izi is a facial cycle of n such that Q0ji has not any common vertex with each of R0,1,..., R0,t, R0,1,..., R'0,t. Then there is a supergraph H of G satisfying the following conditions: (i) E' is an edge subset of E(H). (ii) H has an embedding on the orientable surface of genus g + 2t2 such that it has a set of tfacial 3-cycles {Qtji | Qtji = y^x2i-1 x2iyii,i = 1,2,... ,t}, where yii is some vertex in {y4i-3,y4i-2,y4i-1 ,yn | i = 1,2,...,t}. X2-zt X2t—ljf---------- X2< x1 Figure 1: A local structure in n. Remark 2.2. (1) A local structure of n is shown in Figure 1. (2) An application of Lemma 2.1 to the construction of an embedding of Cm + Kn is as follows. After an embedding of a spanning subgraph of Cm + Kn on some orientable surface has been constructed, all the rest edges of Kn and some edges between Cm and Kn can be attached by applying Lemma 2.1. 226 Ars Math. Contemp. 17(2019)203-222 Proof. We shall construct an embedding on the surface of genus g + 2t2 from the embedding n by applying the operation of adding tubes t times. Every time 2t tubes are added to the present surface. For i = 1, 2,..., t, the tube To,i is added between Q0,i and Ry. Next, the five edges woX2i, X2i-iy4i-3, x2i-iy4i-2, x2iy4i-3 and x2iy4i-2 are drawn on To,i in the way shown in (1) of Figure 2. For i =1,2,... ,t, let QO i = y4i-2X2i-iX2iy4i-2. Zi X2 i-1 X2i wo y4i-3 V4i-2 (1) y4i-2 X2i-1 X2i Wo y4i-1 V4i (2) Figure 2: Two drawings of five edges on a tube. For i = 1, 2,..., t, the tube TO i is added between QO i and R i. Next, the five edges woX2i-i, X2i-iy4i-i, X2i-iy4i, X2iy4i-i and X2iy4i are drawn on T^ in the way shown in (2) of Figure 2. Need to say that the rectangle represents a tube and that the two dot curves are identified with each other in Figure 2. In the rest of the paper we always use a rectangle to represent a tube and the two dot curves in the rectangle are always identified with each other. For the convenience of argument, the way of drawing edges shown in (i) of Figure 2 is called the drawing ofType-i for i = 1,2. To help the readers to understand how those 2t tubes are added and how five edges are drawn on each tube, we give an example that t = 5 which is shown in Figure 3. The diagrams in Figure 3 are partitioned into four columns from left to right. The three rectangles in the first column respectively represent T0 i, T0 2 and T0,3 from top to bottom, and the two rectangles in the third column respectively represent T0,4 and T0,5 from top to bottom. Similarly, the three rectangles in the second column respectively represent T0,i, To,2 and T0,3, and the two rectangles in the fourth column respectively represent Tq,4 and Tq,5 . After those 2t tubes have been added, there are three sets of facial 3-cycles which are Xi = {Qi,i | Qi,i = y4i-ix2i-ix2iy4i-i, i = 1, 2,..., t}, Yi = {Ri,i | Ri,i = x2i-iy4i-3y4i-2x2i-i, i = 1, 2,..., t}, and Yi = {R'i Ri x2iy4i-iy4ix2i, i = 1,2,..., t}. For the convenience of argument, we now define t permutations. For k = 0,1,..., t — 1, we define the permutation Tk on the set {1,2,..., t} as follows. For i = 1,2,..., t, Tk(i) = i + ( —1)fc+ik (mod t), where 0 < i + ( —1)k+ik < t — 1. Obviously, t0 is the identity mapping on {1, 2,..., t}. For 0 < k < t — 1, we define 1 (i) = _\ Tk (i) (mod t), I toti ••• Tk(i) (mod t), if k = 0, if1 k t 1, D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 227 Z3 X5 X6 V10 X5 X6 \ \ / w0 V9 V10 wo V11 V12 Figure 3: The first operation of adding 2t tubes when t = 5. where 0 < rk(i) < t - 1 and r0rl ■ ■ ■ rk is the product of r0,rl,... ,rk in this order. For example, ToTi(l) = ti(to(1)) = 2. Thus, Ql,i, Rl,i and R'1,i can be alternately expressed as follows: Ql,i = (i)-lx2i-lx2iy4r0 (i)-l> Ri,i = X2i-iy4r0(¿)-3y4r0(i)-2X2i-i, and R'l,i = X2»y4r0 (i)-iy4T0 (i)X2i. We continue to add tubes, and consider two cases. Case 1: t = 1 (mod 2). In this case we firstly add t tubes Tl,l,..., Ti,t to the present surface such that T1l,i is between Ql,i and Rl,Tl(¿). Note that Rl,T!(i) = x2n(i)-iy4T0T1 (i)-3y4T0n(i)-2x2T1 (i)-l, i.e., R1,ti (i) = x2ti (i)-ly4T' (i)-3y4T' (i)-2x2Ti (i)-l. For i = 1, 2,..., t, the five edges x2i-iy4T; (i)-3, £2i-iy4T; (i)-2, £2iy4Ti W-3, x2i(i)-2 and x2ix2Tl(i)-l are drawn on T^ in the way of the drawing of Type-1. Thus, there is a set Xi of t facial 3-cycles, where Xi = {Qi,i 1 Qi,i = ^4t'(i)-2x2i-lx2i^4t'(i)-2, i = 1 2, . . . ,t}. Next, the t tubes T',l;..., T',t are added to the present surface such that T'l,i is between Qi,i and R,Ti(i). Then the five edges x2i-iy4T;(i)-i, £2i-iy4T;(i), £2^4^'(i)-i, x2iy4T{(i) 228 Ars Math. Contemp. 17 (2019) 223-253 X3 V5 V6 X4 V7 V8 X7 X8 V18 X7 X8 i v >/ 7 A : /. ( V17 V18 X10 V1g V20 V10 X3 X4 V2 Xg xio V11 V12 X2 V3 V4 X5 X6 V14 X5 X6 I' V >1 7 A ( V13 V14 X8 V15 V16 Figure 4: The second operation of adding 2t tubes when t = 5. and x2ix2Tl (^ are drawn on T[ i in the way of the drawing of Type-2. For example, if t = 5, the above operation of adding 2t tubes is shown in Figure 4. The order of diagrams in Figure 4 is as that in Figure 3. After those 2t tubes have been added, there are three sets X2, Y2, and Y2 of facial 3-cycles which are X = {Q2,i | Q2,i = V4t[ (i)-lX2i-lX2iV4r[ (i)-1, i = 1, 2, . . . , t}, Y2 = {R2,i | R2,i = X2i-iy4r{ (i)-3VAr[ (i)-2%2i-1,i = 1, 2, . . . ,t}, and Y2 = {R2 ,i I R2,i = x2iV4r{ (i)-iV4ri (i)X2i, i = 1, 2, . . . ,t}. In general, if the s-th operation (s > 1) of adding 2t tubes has been applied, then there are three sets of facial 3-cycles, i.e., X = {Qs,i | i =1,2,.. .,t}, Ys = {Rs,i | i = 1,2,... ,t}, and YS = {RS,i I i = 1,2,..., t}. Next, we apply the (s + 1)-th of adding 2t tubes Ts,1,..., Ts,t, Ts',1,..., Ts',t to the present surface satisfying the following conditions. (1) If 1 < s < t-2i, then the tube Ts,i is added between Qs,i and Rs,Ts(i), where i = 1, 2, . . . ,t. In this case Rs,Ts(i) = x2Ts(i)-iV4T's (i)-3V4T's (i)-2x2Ts(i)-1. Next, D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 229 the five edges x2i-lVAr's (i)-3, x2i-lV4r£(i)-2, x2iV4rS (i)-3, X2iV4r's (i)-2, and X2iX2Ts(i)-1 are drawn on Ts (i)-2, i = 1, 2,...,t}. For i = 1,2,... ,t, the tube T'^ is added between Q's i and R's T (i). Note that R's Ts(i) = X2TS(i)V4T>s(i)-iV4T>(i)X2Ts(i). Next, the five edges X2i-1V4T> (i)-1, X2i-lV4Ts (i), X2iV4T's (i)-1, x-2iV4Ts (i), and X2i-1X2TS (i) are drawn on T'^ in the way of the drawing of Type-2. After the (s + 1)-th operation of adding 2t tubes has been applied, there are three sets Xs+1, Ys+1, and Y's+1 of facial 3-cycles which are Xs + 1 = {Qs+1,i I Qs+1,i = V4t's (i)-1x2i-1X2iV4T's (i)-1, i = 1, 2, . . . ,t}, Ys+1 = {Rs+1,i I Rs+1,i = X2i-1V4T'S(i)-3V4T's(i)-2X2i-1, i = 1,2,...,t}, and ys + 1 = {Rs +1,i 1 Rs + 1,i = x2iV4T's (i) — 1 y 4t' (i)x2i, i = 1, 2,...,t}. (2) If t++1 < s < t - 1, suppose that k and k' are the maximum even and odd numbers which are not more than , respectively. There are two cases to consider. If s = m, m + 2,..., m + k, then the tube TsA is added between QsA and Rs Ts (i). Next, the five edges x2i-1y4Ts (i)-1y X2i-W4Ts (i), x2iy4Ts (i)-1, x2i'y4Ts (i), and x2iX2TS (i) are drawn on Ts s2. Since t'(i) = r0r1 • • • ts(i) (mod t) and Tj (i) = i + (-1)j+1j (mod t), we have that tSi (i) = i + Ell0(-1)fc+1k = tsS2 (i) = i + ESI0(-1)1+11(modt). Hencess EHo(-1)fc+1k = o(-1)1+11 (mod t). Thus, KU^-1)^ = 0 (mod t). Since 1 < s1 < t - 1, we have that Ek1 +1(-1)k+1k = 0 (mod t). Z- k=S2 + 1 Then there is a contradiction. Thus, the proposition is verified. Claim 2.6. H contains the edge set {xjXj+1,... ,XjX2t | i = 1, 2,..., 2t - 1} \ {x2i-1x2i | i =1, 2,..., t}. In fact, there are 2t edges being added such that each has the form xkXj (k = j) except for the form x2i-1x2i after the (s + 1)-th operation of adding 2t tubes has been applied, where 1 < s < t - 1. So there are 2t(t - 1) edges of the form xixj being added after the t-th operation of adding tubes has been applied. We now show that any two edges in those 2t(t - 1) edges are different. We need the following proposition. Proposition 2.7. Suppose that s1 and s2 are two distinct integers such that 1 < s1; s2 < t - 1. If s1 + s2 = 0 (mod t), then TS1 (i) = ts2 (i). In fact, TS1 (i) = i +(-1)Sl+1s1 = i + (-1)i-S2+1(t - s2) = i +(-1)t-S2s2 (mod t). Since t = 1 (mod 2), (-1)t-S2 = (-1)S2+1. So TSl (i) = i + (-1)S2+1s2 (mod t). In other words, TSl (i) = ts2 (i). According to the rule of the (s + 1)-th operation of adding 2t tubes, x2i and x2i-1 are respectively connected with x2Ts(i)-1 and x2Ts(i) if 1 < s < i-1, and x2i and x2i-1 are respectively connected with x2Ts(i) and x2Ts(i)-1 if ^^ < s < t - 1. By Proposition 2.7, the pair of vertices connected with the pair of x2i-1 and x2i in the s2-th operation of adding 2t tubes is the same as the pair connected with the pair of x2i-1 and x2i in the s1-th operation of adding 2t tubes if s1 + s2 = 0 (mod t) and 1 < s1; s2 < t - 1. But the methods of two connections are different. We now view the pair of x2i-1 and x2i as a vertex ui, where i G {1,2,... ,t}. In order to show Claim 2.6, it is sufficient to show that is connected with , where p, q G {1, 2,..., t} and p = q. For the purpose, it is sufficient to show that there exists some k such that Tk (p) = q or Tk (q) = p. By Proposition 2.7, it is sufficient to show that for any D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 233 two distinct number i, j G {1,2,..., t}, there exists some k G {1,2,..., } such that Tfc(i) = j (mod t) or rfc(j) = i (mod t). Without loss of generality, suppose that j > i. If j - i = 1 (mod 2), there are two cases to consider. If j - i < i-1, let k = j - i. Then Tk(i) = i + (-1)fc+1k = i + (j - i) = j (mod t). So Tfc (i) = j. If j - i > i+i, let k = t - (j - i). Then Tk(i) = i + (-1)fc+1k = i - t + j - i = j (mod t). So Tk (i) = j .If j - i = 0 (mod 2), there are two cases to consider. If j - i < i-1, let k = j - i. Then Tfc(j) = j + (-1)fc+1k = j - (j - i) = i (mod t). Thus, Tk (j) = i. If j - i > ii-1, let k = t - (j - i). Then Tfc(j) = j + (-1)fc+1k = j +1 - j + i = i (mod t). So Tfc (j) = i. Therefore, is connected with , where p = q. Thus, Claim 2.6 has been proved. Case 2: t = 0 (mod 2). We proceed the similar argument to that in Case 1. Let Xs, Ys, and YS be the sets of facial 3-cycles defined in Case 1. When the (s + 1)-th operation of adding 2t tubes Ts,1,..., Ts,t, Ts' 1;..., Ts',t will be applied, it satisfies the following conditions. (1) If 1 < s < - - 1, then the ways of adding 2t tubes and drawing the five edges are similar to that in (1) of Case 1. (2) If s = |, we consider two cases. If 1 < i < -, then the tube Tt ,j is added between Q±and Rt ,T (j), and the five edges x2i-1y4r; (i)-3; x2i-1y4r; (i)-2, x2iy4rt (i)-3; 2 2 2 X2iy4r2 (i)-2, and X2j-1X2tt (j)-1 2 2 are drawn on Tt ,j in the way of the drawing of Type-1. If | + 1 < i < t, then the tube Tt is added between Q t and R't and the 2 1 — — ' 2 2 t ,T t (i)' five edges 2 x2i-1y4Tt (i)-1; x2i-1y4rt (i), x2iy4rt (i)-1; 2 22 X2iy4rt (i), and X2iX2rt (i) 2 2 are drawn on Tt in the way of the drawing of Type-1. After those t tubes have been added, there is a set X£ of t facial 3-cycles, where 2 Xt = {Q't , | Q'tj = y4rt (i)-2X2i-1X2iy4Tt (i)-2, if i = 1, 2, ..., 2, or 2 2 > 2 > 2 2 Q't j = y4rt (i)X2i-1X2iy4r2 (i), if i = 2 + 1, 2 + 2, . . . , t - 1}. 2 ' 2 2 234 Ars Math. Contemp. 17 (2019) 223-253 Next, if 1 < i < |, then the tube Tt . is added between Q't . and R't ,.,., and the 2 2 >® 2 2 ,T2 (i) five edges x2i-iy4T; (i)-i, x2i-iy4T; (i), £2.^2 (i)-i, 2 2 2 x2iy4T't (i), and x2i-iX2Tt (i) 2 2 are drawn on Tt . in the way of the drawing of Type-2. If | + 1 < i < t, then the 2 >i 2 tube T2 i is added between Q't i and R2 ,T2 (i), and the five edges x2i-iy4T2 (i)-3> x2i-iy4T2 (i)-2; x2i^4T' (i)-3, 2 22 X2i y4T 2 (i)-2, and £2i-i£2T2 (i)-i 2 2 are drawn on T2 . in the way of the drawing of Type-2. There are three sets X2+i, 2 2 + Y2+i, and Y2 ,1 of facial 3-cycles, where 2 + 2 +i +i = {Q * +i,i 1 Q * +i,i = ^4t; (i)-ix2i-ix2iy4T; (i)-i, if i = 1, • • •, 2, or 2 2 Q 2 + i,i = y4T 2 (i)-3x2i-ix2iy4T 2 (i)-3; if i = 2 + 1; • • • ji}; 2 2 Y2 + i = {R2 +i,i 1 R2 +i,i = x2i-iy4T2 (i)-3y4T2 (i)—2x2i — i; if i = 1; • • • , 2, or 2 2 R2+i,i = x2i-iy4T2 (i)-iy4T2 (i)x2i-iif i = 2 + 1 • • •,t}, 2 2 Y2+i = {R'2+i i | R'2+i i = x2iy4T2 (i)-iy4T2 (i)X2i, if i = 1, • • •, 2, or 2 2 ' 2 ' 2 2 R'2 + i i = x2i^4T2 (i)-3y4T2 (i) — 2x2i if i = 2 + 1 • • • ,t} 2 ' 2 2 (3) If 2 + 1 < s < t - 1, then the tube TSji is added between QSji and RS T (i). Since R' has two forms, we say that S,Ts (i ) • RS,Ts(i) is of Class 1 if RS,Ts(i) has the form ^i^(i)-iy4TS (i)£2i, and • RS,Ts(i) is of Class 2 if RS^^ has the form x2iy4Ts'(i)-3^4TS(i)-2X2i. Similarly, we say that • Rs,Ts(i) is of Class 1 if Rs,Ts(i) has the form x2i-iy4TS«-i^(i)£2i-i, and • Rs,Ts(i) is of Class 2 if Rs,Ts(i) has the form £2.-^4^(0-3^(i)-2X2i-i. If R's T (i) is of Class 1, then the five edges x2i-iy4TS (i)-i> x2i-iy4TS (i); x2i^4TS (i)-i> x2i^4T^ (i), and x2iX2Ts(i) are drawn on TS,. in the way of the drawing of Type-1. If RS T (i) is of Class 2, then the five edges s x2i-iy4T^ (i)-3? x2i-iy4T^ (i)-2 ? (i)-3, x2.y4Ts' (i)-2, and x2iX2Ts(i) 2 D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 235 are drawn on Ts i in the way of the drawing of Type-1. Then there is a set Xs' of t facial cycles, where Xs' = {QS,i I Qs,i = y4rs(¿)-2X2i-iX2iy4rs(i)-2, if RS,rs(i) is of Class 1, or QS,i = V4t's(¿)X2i-iX2iy4r^(i), if RS,rs(i) is of Class 2}. Next, the tube Ts' i is added between QS i and RS,Ts(i). If RS,Ts(i) is of Class 1, then the five edges x2i-iy4TS (i)-ij x2i-iy4Ts' (i)j x2i^4TS (i)-ij x2iy4Ts' (i), and x2iX2Ts(i) are drawn on Ts' i in the way of the drawing of Type-2. If RS,Ts(i) is of Class 2, then the five edges x2i-iy4TS (i)-3, x2i-iy4Ts' (i)-2j x2i^4TS (i)-3, x2iy4Ts' (i)-2, and x2iX2Ts(i) are drawn on TS i in the way of the drawing of Type-2. Then there are three sets XS+i, YS+i and YS+i of t facial cycles, where Xs + 1 = {Qs + i,i I Qs+i,i = ^4tS(i)-2X2i-iX2iy4TS(i)-2, if RS,Ts(i) is of Class 1, or Qs+i,i = y4Ts'(i)X2i-iX2iy4TS(i), if Rs,ts(i) is of Class 2}, Ys+i = {Rs+i,i I Rs+i,i = x2i-iy4TS(i)-3^4TS(i)-2X2i-i, if Rs,TS(i) is of Class 1, or Rs+i,i = x2i-iy4T^ «-1^ (i)X2i-i, if Rs,Ts(i) is of Class 2}, YS + 1 = {RS+i,i 1 RS + i,i = x2i^4T^(i)-3^4Ti(i)-2x2i, if RS,Ts(i) isofClass 1, or RS+i,i = x2i^4T^ (i)-iy4Ti(i)X2i, if RS,ts (i) is of Class 2}. The above operation of adding 2t tubes is not stopped until the t-th operation of adding 2t tubes has been applied. Let n' be the obtained embedding and let H the graph corresponding to n'. Clearly, n' is an embedding on the orientable surface of genus g + 2t2, and n' has a set Xt of t facial 3-cycles in which each has the form Qiji = x2i-1x2iy;., where ^ e {y4j-3, y4j-2, y4j-i,y4j I j = 1,2, ...,t}. In order to help readers to understand the procedure of adding tubes in this case, we give an example that t = 4 which is shown in Figure 6. For i = 1,2, 3,4, the four rectangles in the first column of (i) respectively represent Ti i,..., Ti 4 from top to bottom, and the four rectangles the second column of (i) respectively represent Ti' 1,..., T/ 4 from top to bottom. We need to show that H satisfies the demands of the theorem. Obviously, w0 is connected with each of x1, x2,..., x2t in H. By the similar argument as in Case 1, one can show that for i = 1,2,..., 2t and j = 1, 2,..., 4t, xi is connected with y- in H. Claim 2.8. H contains the edge set {xixi+i,... ,XiX2t | i = 1, 2,..., 2t - 1} \ {x2i-ix2i I i = 1, 2,..., t}. 236 Ars Math. Contemp. 17 (2019) 223-253 zi Xi X2 y2 Xl X2 y3 xi X2 y6 xi X2 wo yi y2 wo y3 y4 Z2 X3 X4 y6 X3 X4 wo y5 y6 wo y7 ys Z3 X5 X6 yio X5 X6 Z4 X7 Xs yi4 X7 Xs r X X3 y5 y6 X4 y7 y7 X3 X4 yio X3 X4 i. X5 y9 yio X6 yii yi2 yii X5 X6 yi4 X5 X6 wo y9 yio wo yii yi2 x7 yi3 yi4 Xs yi5 yi6 yi5 X7 xs y2 X7 xs t wo yi3 yi4 wo yi5 yi6 xi yi y2 X2 y3 y4 (1) (2) y7 xi X2 yi4 xi X2 yi5 xi X2 yio xi X2 f % f X7 yi y2 xs y3 y4 yi5 X5 X6 ys X5 X6 X2 y7 ys Xi y5 y6 y3 X7 Xs yi2 X7 Xs ( (3) Y\ X5 yi3 yi4 X6 yi5 yi6 xs y9 yio X7 yn yi2 yii X3 X4 y2 X3 X4 y3 X3 X4 yi6 X3 X4 t X2 yi5 yi6 xi yi3 yi4 y5 X5 X6 y4 X5 X6 X4 y3 y4 X3 yi y2 y9 X7 xs y6 X7 xs X4 yii yi2 X3 y9 yio X6 y5 y6 X5 y7 (4) Figure 6: The operations of adding 21 tubes when t = 4. D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 237 We proceed the similar argument to that in Claim 2.6. Obviously, there are 2t(t - 1) edges of the form xkxj (k = j) except for the form x2i-ix2i after the t-th operation of adding 2t tubes has been applied. According to the rule of the (s + 1)-th operation of adding 2t tubes, x2j and x2i-1 are connected with x2Ts(i)-1 and x2Ts(j), respectively, if 1 < s < 2 - 1 or s = 2 and i =1,2,..., 2, and x2j and x2i-1 are connected with x2Ts(j) and x2Ts(i)_1, respectively, if 2 + 1 < s < t - 1 or s = | and i = 2 + 1, 2 + 2,...,t. We now consider the relation between tsi (i) and ts2 (i), where 1 < s1; s2 < t - 1 and s1 + s2 = 0 (mod t). We have the following proposition. Proposition 2.9. Suppose that s1 and s2 are two integers such that 1 < s1; s2 < t - 1. If s1 + s2 = 0 (mod t), then tsi (t - i) = t - ts2 (i) or ts2 (i) = t - tsi (t - i). In fact, tsi (t - i) = t - i + (-1)Sl+1s1 = t - i +(-1)t_S2+1(t - s2) = t - i + (-1)t_S2s2 (mod t). Since t = 0 (mod 2), (-1)t_s2 = (-1)s2. So tsi (t - i) = t - i + (-1)s2s2 = t - (i + (-1)S2+1s2) = t - ts2(i) (mod t). In other words, tsi (t - i) = t - ts2 (i), or ts2 (i) = t - tsi (t - i). Thus, the pair of vertices of the form x2t (i)_1 and x2t (j) connected with the pair of x2i-1 and x2i in the (s2 + 1)-th operation of adding 2t tubes is the same as the pair of vertices of the form x2(t_T (i_j))_1 and x2(t_T (t_i)) connected with the pair of x2i-1 and x2i in the (s1 + 1)-th operation of adding 2t tubes if 0 < s1; s2 < t -1 and s1 + s2 = 0 (mod t). But the methods of two connections are different. We now view the pair of x2i_1 and x2i as a vertex uj, where i G {1,2,..., t}. In order to show Claim 2.8, it is sufficient to show that is connected with , where p, q G {1,2,..., t} and p = q. For the purpose, it is sufficient to show that there exists some k such that Tk (p) = q or Tfc(q) = p. By Proposition 2.9, it is sufficient to show that for any two distinct numbers i, j G {1, 2,..., 2}, there exists some k G {1,2,..., t} such that Tk (i) = j or Tk(j) = i. Without loss of generality, suppose that j > i. If j - i = 1 (mod 2), let k = j - i. Then Tfc(i) = i + (-1)fc+1k = i + (j - i) = j (mod t). So Tk (i) = j. If j - i = 0 (mod 2), let k = j - i. Then Tfc(j) = j + (-1)fc+1k = j - (j - i) = i (mod t). So Tk (j) = i. Hence is connected with for p = q. Thus, Claim 2.8 has been proved. Therefore, the obtained embedding is as required. □ In the proof of Lemma 2.1, we apply the operation of adding 2t tubes t times starting from X0, Yo and Y0 to construct an embedding of H, where X0 = {Qo,i | i = 1, 2,..., t}, Yo = {Ro,i | i = 1,2,..., t}, Y0 = {R0,i I i = 1, 2,..., t}. We call the above procedure the operation of adding 2t2 tubes starting from X0, Y0 and Yo. Lemma 2.10 below is an analogue of Lemma 2.1. The vertex w0 in Lemma 2.1 is replaced with two vertices w'0, W in Lemma 2.10, and the others are not changed. The proof is similar to that in the proof of Lemma 2.1, which is omitted here. 238 Ars Math. Contemp. 17 (2019) 223-253 Lemma 2.10. Suppose that G is a graph which has a vertex subset , z!,z2,...,zt}u{xi | i = 1, 2, .. ., 2t} U {yj | j = 1, 2, .. ., 4t}, where zi, z2,..., zt need not be different, and suppose that G contains no edges in the set E' = {w0x2i-i, w0'x2i | i = 1, 2,..., t} U {xiyj | i =1, 2,..., 2t; j = 1, 2,..., 4t} U ({xjxi+i, ... ,xjx2t | i = 1, 2,. .., 2t - 1} \ {x2i-ix2i | i = 1, 2, ... ,t}). Suppose that n is a 2-cell embedding of G on the orientable surface Sg with the following properties: (i) For i = 1, 2,..., t, R0,i = w'0 y4i-3y4i-2w0 and R0,i = w0'y4i-iy4iw0 are facial cycles of n. (ii) For i = 1,2,..., t, Q0,i = zi x2i_1x2izi is a facial cycle of n such that Q0,i has not any common vertex with each of R0,1,..., R0,t, R0,1,..., R0,t. Then there is a supergraph H of G satisfying the following conditions: (i) E' is an edge subset of E(H). (ii) H has an embedding on the orientable surface of genus g + 2t2 such that it has a set oftfacial 3-cycles {Qt,i | Qt,i = ylix2i-1x2iy;., i = 1,2,... ,t}, where yli is some vertex in {y4i-3, y4i-2,y4i-i,y4i | i = 1,2,... ,t}. We now introduce another method of constructing an embedding, which is used in the proof of Lemma 2.11. Lemma 2.11. Let k and l be two positive integers. Suppose that G has a vertex subset {w, z} U {xi, yj | i =1, 2, ..., 2l, j = 1, 2, .. ., 2k}, and suppose that G contains no edges in E' = {xiyj | i = 1, 2,..., 2l, j = 1, 2,..., 2k}. If G has a 2-cell embedding n on the orientable surface Sg such that Fi = wx2i-1x2iw and Fj = zy2j-1 y2j- z are facial cycles in n for i = 1,2,..., l and j = 1, 2,..., k, then there is a supergraph H of G with the following properties: (i) E' is an edge subset of H. (ii) H has an embedding on the orientable surface of genus g + kl such that it has a set of l facial 3-cycles in which each has the form yhix2i-1x2iyhi, where yhi G {yi,y2,... ,y2k}. Proof. We construct an embedding from n as follows. (1) Let D1,1 = F^ Then the tube Ti^ is added between D1,1 and F1. Next, the four edges x1y1, x1y2, x2y1 and x2y2 are drawn on T11,1 in the way shown in Figure 7. Let D1,2 = y1x1x2y1, and let Q1,1 = x2y1y2x2. The tube T11,2 is now added between D12 and F2', and the four edges x1y3, x1y4, x2y3 and x2y4 are drawn on it in the similar way as in Figure 7. Let D1,3 = y3x1x2y3 and Q1,2 = x2y3y4x2. Then D13 and F3 are dealt with as D12 and F2, and so on. The procedure is not stopped until Fk has been dealt with. Thus, we obtain k facial cycles Q1,1,..., Q1,k, where Q1,i = x2y2i-1y2ix2. Moreover, both x1 and x2 are connected with each of yi,y2,... ,y2k. D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 239 Figure 7: The drawing of the four edges in Ti,i. (2) Let Qi = |Qi,i, Qi,2,..., Qi,k}. Then the tube T2,i is added between F2 and Qi,i, and the four edges x3y1; x3y2, x4y1 and x4y2 are drawn on it in the similar way as in Figure 7, and so on. The procedure is stopped till Qi,k has been dealt with. Then we obtain a set of facial walks Q2 = {Q2,i, Q2,2,..., Q2,k} such that Q2,j = x4y2i-iy2jx4. Moreover, both x3 and x4 are connected with each of yi; y2,..., y2k. (3) Q2 and F3 are dealt with in the similar way to that of Qi and F2, and so on. The procedure is stopped till Fi has been dealt with. Then x is connected with each of yi, y2,..., y2k for i = 1,2,..., 21, and there is a set of 1 facial 3-cycles in which each has the form yh.x2i-ix2iyh.. Moreover, there are kl tubes to be added to the primitive surface all together. So the obtained embedding n' is one on the orientable surface of genus g + kl. Let H be the graph corresponding to n'. It is easy to find that E' is an edge set of H. □ Let Fi = {Fi, F2,..., Fi}, and let F2 = {Fi, F2,..., Fk}. We call the procedure of constructing an embedding in the proof of Lemma 2.11 the operation of adding tubes with respect to F1 and F2. 3 An upper bound for 7 (Cm + Kn) if m is odd From now on we always suppose that m > 3 and n > 4, that Cm = m1m2 ... Mmui, and that the vertex set of Kn is {vi; v2,..., vn}. If no confusion occur, a face and its boundary in an embedding are not distinguished in the rest of the paper. Lemma 3.1. Suppose that m = 1 (mod 2) and n = 0 (mod 4). If m > 4n — 5, then Y(Cm + K„) < (m - 2)(n - 2) 4 Proof. We shall construct an embedding of Cm + Kn on the oreintable surface of genus (m-2)(n-2) 4 ] in the following steps. (1) In the step we shall construct an embedding on a sphere in which each of vi and v2 is connected with each of ui, u2,..., um, and each of ui and u2 is connected with each of vi; v2,..., vn. First, Cm is placed in the equator of the sphere, and both vi and v2 are situated at the northern pole and the southern pole, respectively. Second, each of vi and v2 joins to 240 Ars Math. Contemp. 17 (2019) 223-253 each of u1, u2,..., um, and the path P = v3v4 ... vn is placed in the interior of the face v1u1u2v1 such that v3 is near to v1. Third, v3 joins to v1, and each of u1 and u2 joins to each of v3, v4,..., vn. Thus, we obtain an embedding n1 on the sphere, which is shown in Figure 8. Figure 8: The embedding n1. (2) In the step we shall add n tubes to the sphere such that u3 is connected with each of v3, v4,..., vn, and v1 joins to v2. The tube T1 is now added between the facial cycles u2v3v4u2 and v2u2u3v2. Next, the edge u2 v3 is redrawn such that it is on and a segment of local rotation at u2 in clockwise is that v4, v1; u3, v3. Then there is a facial walk W1 = u3v2u2v3v1u2v4 v3u2u3. Let Z1 = u3v2u2v3v1 u2v4v3. Then W1 = Z1u2u3. The tube T2 is added between the facial cycle u2v8v7u2 and W1. Then the two edges u2v7 and u2 v6 are redrawn on T2 such that a segment of local rotation at u2 in clockwise is that u3, v7, v6, v3. Thus, there is a facial walk W2 = Z1u2v6v5u2v8v7u2u3. Let Z2 = u2v6v5u2v8v7. Thus, W2 = Z1Z2u2u3. For i = 3,4,..., n, the tube Ti is added between the facial cycle u2v4iv4i-1u2 and Wi-1. Next, both edges u2v4i-1 and u2v4i_2 are redrawn on Ti such that a segment of local rotation at u2 in clockwise is that u3, v4i-1, v4i_2 and v4i_5. Then there is a facial walk Wi = Z1Z2... Zi_1u2v4i_2v4i_3u2v4iv4i_1u2u3. Let Zi = u2v4i_2v4i_3u2v4iv4i_1. Thus, Wi = Z1Z2 ... Z^u3. After the tube Tn has been added, there is a facial walk Wn = Z1Z2... Zn_1u2u3. For i = 2, 3,..., n, each of v4i_3, v4i_2, v4i-1 and v4i appears in Zi once, but it does not appear in Zj if i = j. Also, v4 appears in Z1 once, but it does not appear in Zj if j = 1. In the interior of the face Wn, u3 joins to each of v4, v5,..., vn, and v1 joins to v2. For example, if n = 8, W2 and all added edges in the interior of W2 are shown in Figure 9. Let n2 be the embedding obtained from n1 by the above operation of adding tubes. Then n2 is an embedding on the surface of genus n. (3) In the step we shall add 2( n — 1)2 tubes to the present surface satisfying the following conditions: (i) v1 is connected with each of v3, v4, , v„, D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 241 Figure 9: W2 and all edges added in the interior of W2. (ii) for i = 3,4,..., n and j = 4,5,..., 2n — 1, v is connected with Uj, and (iii) all edges in the set {ViVi+1, ..., VjV„ | i = 3,. .., n — 1} \ {v2i+iV2i+2 | i = 1, .. ., f-2 } are added. For the above purpose, let Xo = {Qo,i | Qo,i = MiV2i+iV2i+2Mi, i = 1, 2,..., f — 1}, Yo = {Ro,i | Ro,i = viM4jM4i+ivi, i = 1,2,..., 2 — 1}, and Y0 = {Ro,i I Ro,i = ViW4i+2«4i+3Vi, i =1, 2,..., 2 — 1}. Then we apply the operation of adding 2(2 — 1)2 tubes starting from Xo, Yo, and Yo. By Lemma 2.1, an embedding n3 is obtained which satisfies all the requirements and contains a set Ao = {Ao,i, Ao,2,..., Ao,n-i} of facial 3-cycles such that Ao,j has the form ukiv2i+iv2iuki, where uki G {uj | j = 4,5,..., 2n — 1}. (4) In the step we shall add 2( 2 — 1)2 tubes to present surface satisfying the following conditions: (i) v2 is connected with v3, v4,..., vn, (ii) for i = 3,4,..., n and j = 2n, 2n + 1,..., 4n — 5, v is connected with Uj. For the above purpose, let Bo = {Bo,i I Bo,i = v2U2„+4i-4U2n+4i-3V2, i = 1,2,..., f — 1}, and Bo = {B'I B'= V2U2„+4i-2U2n+4i-iV2, i = 1, 2, . . . , | — 1}. We now apply the operation of adding 2(f — 1)2 tubes starting from Ao, Bo, and B'. By Lemma 2.1, an embedding n4 is obtained which satisfies all the requirements and contains a set F = {Fi, F2,..., Fn-i} of facial 3-cycles such that F has the form uli v2i+iv2i+2u;i, where uli G {uj | j = 2n, 2n + 1,..., 4n — 5}. At last, all edges of the form VjVj added in the above operations are deleted, since these edges have been existed. Note that the deletion of these edges does not affect each cycle in . 242 Ars Math. Contemp. 17 (2019) 223-253 (5) If m = 4n — 5, then there is nothing to do. If m > 4n — 5, then we shall add tubes to the present surface such that v is connected with each of U4n_4, . . . , Um for i = 3,4,..., n. Let D = {Di | Di = ViM4n+2i-6M4n+2i-5Vi, i = 1, 2, . . . , m-4"+5 }. We now use the operation of adding tubes respect to F and D. By Lemma 2.11, there are ("-2)("4-4"+5) tubes being used, and vi is connected with u, where i G {3,4,..., n} and j G {4n — 4,4n — 3,..., m}. Let n5 be the obtained embedding. Then it is an embedding of Cm + Kn on the surface of genus n (n — 2)2 (n — 2)2 (n — 2)(m — 4n + 5) 4 + 2 + 2 + 4 . By simple counting, we have that n (n - 2)2 (n - 2)2 (n - 2)(m - 4n + 5) 4 + 2 + 2 + 4 n (n - 2)(m - 3) 4 + 4 ' Since n = 0 (mod 4), (m - 2)(n - 2)" "n - 2" 4 4 (n - 2)(m - 3) n (n - 2)(m - 3) + 4 = 4 + 4 ' So n (n - 2)2 (n - 2)2 (n - 2)(m - 4n + 5) 4 + 2 + 2 + 4 (m - 2)(n - 2) Hence, 7(Cm + K„) < [ (m-24("-2) ]. Lemma 3.2. Suppose that m = 1 (mod 2) and n = 2 (mod 4). If m > 4n — 3, then □ Y(Cm + Kn) < (m - 2)(n - 2) 4 Proof. We construct an embedding of Cm + Kn in the similar way to that in the proof of Lemma 3.1. (1) First, place Cm, vi, and v2 on a sphere and add edges as (1) in the proof of Lemma 3.1. Let Fi = viwi^vi, F2 = viM2U3V1, and F3 = V1W4W5V1. The path P = v7v8 ... vn is now placed in the interior of Fi, and each of ui and u2 joins to each of v7, v8,..., vn. Next, both v3 and v5 are placed in the interior of F2, and they join to each of u2 and u3, respectively. Similarly, both v4 and v6 are placed in the interior of F3, and they join to each of u4 and u5, respectively. Let ni be the obtained embedding on the sphere, which is shown in Figure 10. The edge w3w4 is now deleted from ni. Then the face v1m3m4v1 and the face v2u3u4v2 are merged into a face F4 = v1u3v2u4v1. Next, the edge v1v2 is drawn in the interior of F4. Let F5 = w2v3w3v5w2 and F6 = w4v4w5v6w4. The tube T1 is added between F5 and F6. Then the five edges are drawn on T1 in the way shown in (1) in Figure 11. Let F7 = w2v3w4v6w2 and F8 = w3v4w5v5w3. Next, the tube T2 is 4 D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 243 Figure 10: The embedding ni. U2 V3 U3 V5 U2 V3 U4 Vq U4 V4 U5 Vq (1) U3 V4 U5 V5 (2) Figure 11: The drawing of edges on T1 or T2. added between F7 and F8. Then the five edges are drawn on T2 in the way shown in (2) in Figure 11. We observe that the local rotation at u2 in clockwise is that u1, vn,..., v1; v3, v4, v6, v5,u3,v2. Let F9 = u2 v6u3v4u2, which is a facial cycle (refer to (2) in Figure 11). Let F10 = M1v„M2M1 (refer to Figure 10) if n > 6, or F10 = m1v1m2m1 if n = 6. The tube T3 is now added between F9 and F10. Then the edges u2v5 and u2v4 are redrawn on T3 such that a segment of the local rotation at u2 is that «1, v6, v4, vn, v3, v5. Thus, there is a facial walk W1 = m1m2v4v3m2v5m5v6m2v„m1. Next, u1 joins to each of v3, v4, v5, v6, and v5 joins to v6. Then there are two facial cycles Q0,1 = u1v4v3M1 and Q0,2 = u1v5v6M1. (2) If n = 6, there is nothing to do. If n > 6, then we shall add 3("_2) tubes to the present surface such that« is connected with each of v3, v4,..., vn for i = 3,4,5. Let F11 = v1u3v3M2v1 (refer to Figure 10). For i = 1,2,..., , let F/ = u2v4i+4v4i+5u2. The tube T1 is added between F1 and F11. Then two edges u2v4i+4 and u2v4i+5 are redrawn on T1. There is a facial walk W1 = m2v3m3v1m2v9v10m2 v7v8u2. For i = 2,..., , the tube T/ is added between F[ and Wi_1, where Wi_1 is a facial walk which contains v7,..., v4i+2 after T/_1 has added. Next, both u2v4i+4 and u2v4i+5 are redrawn on T/ and a segment in the local rotation at u2 in clockwise is that «4(i_1)+5, «4i+4, «4i+5, and «3. After the tube T^-6 4 has been added, there is a facial walk Wn-6 which contains «3, vr, v8,..., vn. 4 Moreover, each of vr, v8,...,vn appears in Wn-6 once. Next, «3 joins to each 244 Ars Math. Contemp. 17 (2019) 223-253 of v7, v8,..., vn. There are 6 facial 3-cycles D1,D2,..., Dn—6, where Di = U3V2i+5V2i+6U3. Let F12 = u4v4u5u4 (refer to Figure 10). Let F = {F12}, and let D = {D1, D2,..., D n—6}. Using the operation of adding tubes with respect to D and F, each of u4 and u5 is connected with each of v7,v8,... ,vn. By Lemma 2.11, there are tubes being used. Also, there are "t-6■ facial cycles Q0,3,... ,Q0 n—2 in which Q0ji has the form uliv2i+1v2i+2uli, where uli G {u4, u5}. Let n2 be the embedding obtained from n1 by the above procedures. Then n2 is an embedding on the surface of genus 3 + "p + n-6 (= 3(n—2)). Moreover, ui is connected with each of v1,v2,... ,vn fori =4 1,2,..., 5. (3) For i = 1, 2,..., n-6, let R0,j = v1u4j+2u4j+3v1, and let R'0 j = v1 u4j+4u4j+5v1. Let X = {Q0,i+2 | i =1,2,..., }, Y = {R0,i | i = 1, 2,..., }, and Y0 = {R0,i | i = 1, 2,..., }. Next procedures are similar to that in (4) and (5) in the proof of Lemma 3.1. Note that (m-54(n-2) tubes are added to the present surface such that vi is connected with uj for i = 3,4,... ,n and j = 6,7,... ,m. Thus, an embedding n3 of Cm + Kn on the surface of genus 3n4=2- + (m-54(n-2) is obtained. Since n = 2 (mod 4), [ (m-24(n-2) 1 = + (m-54(n-2). Thus, ^ is the desired embedding. Since the operation of adding n - 2 tubes is used twice, m is at least 5 + 4(n - 2) (= 4n - 3). □ Lemma 3.3. Suppose that m = 1 (mod 2) and n = 1 (mod 2). If m > 6n - 13, then Proof. We consider two cases. Case 1: m = 1 (mod 4). In this case we construct an embedding of Cm + Kn in the following steps. (1) The path Pm = u1u2.. .um is placed in the equator of a sphere. The edge v1v2 is situated in the northern pole and the vertex v3 placed at the southern pole. Next, each of v1 and v3 joins to each of u1,u2,..., um+1, and each of v1 and v2 joins to 2 each of um+3, u m+5,..., um. Also, v1 joins to v3, and v2 joins to um+1. Thus, an 22 2 embedding n1 on the sphere is obtained. For example, the embedding n1 is shown in Figure 12 if m = 17. (2) In this step we shall construct an embedding on the surface of genus m-1 such that v. is connected with u1, u2,..., u m—1, v3 connected with u m + 3 , u m+5 , . . . , um, and 2 22 u1 connected with um. For i = 1,2,..., 1, let Fj = v3u2i-1u2jv3 and Fj = v2um+1_2ium+2-2iv2. The tube T1 is added between F1 and F1, and the five edges are drawn on T1 in the way shown in (1) in Figure 13. The tube T2 is added between F2 and F., and the five edges are drawn on T1 in the way shown in (2) of Figure 13. For i = 3,4,..., m-1, the tube Ti is added between Fi and F/. Then the four edges v3um+2-2i,v3um+1-2i, v2u2i-1, and v2u2i are drawn on Ti in the way shown in (2) of Figure 13, but v2v3 is not added. Thus, v3 is connected with each of D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 245 Figure 12: The embedding ni. V3 Ui U2 V3 U3 U4 V2 Um-1 Um (1) V2 Um-3 Um-2 (2) Figure 13: The drawing of edges on T1 or T2. um+3, um+5,..., um, v2. Next, v2 connected with each of u1, u2,..., um-i. Let 2 2 2 n2 be the obtained embedding. Note that there are two sets Z0 and ZQ in n2, where Zq — {ZQ Zo v2U2i-iU2iV2, i — 1,2,..., m-1} and Z0 = {Z0 j | Z0= V3«,m+i_2iwm+2_2iV3, i =1, 2,..., m—}. (3) In this step [] tubes will be added to the present surface such that vj is connected with u m+i, u m+3, u m+5 for i = 4, 5,..., n. 2 2 2 The path P = v4v5 ... vn is now placed in the interior of Z0 m— such that v4 4 is near to v3. Then each of um+3 and um+5 joins to each of v4, v5,..., vn. For 2 2 i =1, 2, . . . , [], let Dj = u m + 3 V4jV4j+iu m + 3 . If n = 1 (mod 4), then [n-4] = n--. The tube T- is now added between D' = v2u m+i u v2 and D1. Next, the edge u m+3 v4 is redrawn on T'. Then we obtain 2 2 2 1 a facial walk W1 which contains u m+i and v4. For i = 2,3,..., , the tube T/ is added between Dj and Wj_ 1, where Wj_ 1 is a facial walk which contains u m+i and 2 u m+i obtained by adding the tube Ti-1. Then two edges u m+3 v4j-1 and um+3 v4j are redrawn on T'. After the tube Tn_ i has been added, there is a facial walk Wn-i j — 4 which contains u m+i, v4,..., vn. Next, u m+i joins to vj if vj appears once in Wn-i 2 2 4 or a copy of vj if it appears more than once in Wn-i. 4 If n = 3 (mod 4), then [n—4] = n-3. We add n-3■ tubes in the similar way to that in the above paragraph. The difference is that two edge u v4j+1 and u m+i v4j+2 246 Ars Math. Contemp. 17(2019)203-222 are redrawn on Ti' for i = 1,2,..., n-3. Let n3 be the embedding obtained from n2 by the above operation of adding tubes. Clearly, um+i, um+3, and um+5 are connected with each of vi, v2,..., vn. 2 2 2 (4) In the step we proceed the similar argument as in (3) and (4) of the proof of Lemma 3.1. Let X0 = {Q0,i | Q0,i = U m+5 V2i + 2V2i + 3U m+5 , i =1, 2, . . . , ^y3}, Yo = {Z0,i | i = 1, 2,..., n-3}, and 2~ n-3\2 Y0 = {Z0,i | i = 1,2,...,^}. Then we apply the operation of adding 2( ^-j3 )2 tubes starting from X0, Y0, and Y0. By Lemma 2.10, we have the following results: (i) v2 is connected with each of v4, v6,..., vn-i, and v3 connected with each of V5, V7,. . . , v„. (ii) For i = 4,5,..., n and j = 1,2,..., n-3, vi is connected with u2j-i, u2j-, um+i-2j, um+2-2j. (iii) There is a set {ViVi+i, . . . , ViV„ | i = 1, 2, . . . , n - 1} \ {V4V5, V6V7, . . . , v„-iv„}. (iv) There is a set A0 = {A0,i, A0,2, . . . , A0, n-3 } of facial cycles such that A0i has the form u;.v2i+iv2iu;., where u;. G {ui,... ,u„-3} U {um -n+4, . . . , um}. Unfortunately, v2 is not connected with each of v5, v7,..., vn and v3 is not connected with each of v4, v6,..., vn-i. In order to attach the edges v2v5,..., v2vn, v3v4,..., v3vn-i, we apply the operation of adding 2( n-3)2 tubes again. Let B0 = {B0,i | B0,i = V3um-„+4-2ium-„+5-2iV3, i = 1, 2,..., n-3} and B0 = {B0,i | B0,i = V2u„-4+2iu„-3+2iV2, i = 1,2,..., 3}. We now apply the operation of adding 2( n-3■ )2 tubes starting from A0, B0 and B0. By Lemma 2.10, we have the following results: (i) v2 is connected with each of v5, v7,..., vn, and v3 connected with each of V4, V6, . . . , V„-i. (ii) For i = 4,5,..., n and j = 1,2,..., n-3, vi is connected with un-4+2j-, un-3+2j, um-n+4-2j , um-n+5-2j . (iii) There is a set L0 = {L0,i, ¿0,2, . . . , L0 n—.} of n-3 facial cycles such that L0,i has the form uhiv2i+iv2iuhi, where uhi G {un-4+2j, un-3+2j , um-n+6-2j, um-n+5-2j 1 j = 1 . . . , 3 }. D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 247 Need to say that all edges of the form vk v; added in the above operations are deleted, since they have been existed. n—3, let Foi = viM2n-7+2iW2n-6+2ivi and F^ = viWm_2n+7-2i 2 For i = 1,2, um-2n+8-2ivi. Let Fo = {Fo| i = 1, 2,..., }, and let FQ = {F^ | i = 1,2,..., n-3}. We apply the operation of adding 2( 2—3)2 tubes starting from L0, F0, and Fq. By Lemma 2.1, v1 is connected with each of v4, v5,..., vn, and there is a set N0 = {N0,1, N0,2,..., N0 n-3 } of 2-3 facial cycles such that N0,i has the form uki v2i+iv2iWfci, where Mfc, € {u2n —7+2j , u2n—6+2jum—2n+7—2j, ura-2„+8-2j | j = 1,..., n~—~}. Next, all added edges of the form vivj- (i, j = 1) are deleted, since they have been existed. (5) In this step we proceed the similar argument to (5) in the proof of Lemma 3.1. For i = 1,...,ii(m-i - 3n + 9), let Mi = viu3n—i 0+2iu3n—9+2ivi, and MQ = viWm-3n+io-2iWm-3n+ii+2ivi. Clearly, M1 -3n+9) is exactly the cycle vium+3um+5 vi. Since um+3 and um+5 are connected with each of vi,..., vn, M1 1 ( m 2 ( -3n+9) should be neglected. Let M = {Mi, M/ | i = 1,..., 2 ( ^ - 3n + 9)}\{M1 ( m-1 -3n+9) }. Next, we apply the operation of adding tubes with respect to M and N0. There are [m—6(n—3)—3](n—3) tubes being added to the present surface. Since m = 1 (mod 2) and n = 1 (mod 4), we have that (m - 2)(n - 2) (m — 3)(n — 3) + m — 1 + n - 4' and [m — 6(n — 3) — 3](n — 3) + m — 1 + n4 + 6 n3 (m — 3)(n — 3) + m — 1 + n4 Hence an embedding of Cm + Kn on the surface of genus [ (m-2)(n-2) ] is obtained. Need to say that the operations of adding 2(2—3 )2 tubes are used three times, m is at least 6(n — 3) (= 6n — 18). If u m+i ,u m+3, u m+5 and M1 (m-i —3n+9) are considered, m is at least 6n — 18 + 5 (= 6n — 13). Case 2: m = 3 (mod 4). In this case we shall construct an embedding of Cm + Kn in the similar way to that in Case 1. (1) Pm, v1, v2, and v3 are placed in a sphere as in Case 1. Next, each of v1 and v3 is connected with each of u1; u2,..., um+i, and each of v1 and v2 is connected with 2 each of u m+3, u m+5,..., um. Also, v2 is connected with u m+i, and v3 is connected 2 2 2 with u m+3. Then we obtain an embedding n1 on the sphere. For example, n1 is shown in Figure 14 if m = 15. 1 4 4 248 Ars Math. Contemp. 17 (2019) 223-253 Figure 14: The embedding ni. (2) As in (2) in Case 1, m-3 tubes are added to the sphere satisfying the following conditions: (i) u1 is connected with um, (ii) v2 is connected with each of u1, u2,..., u m-3, 2 (iii) v3 is connected with each of u m+5, u m+?,..., um. 2 2 Let n2 be the obtained embedding. Then it is an embedding on the surface of the genus m—3. (3) The path P = v4v5 ... vn is now placed in the interior of v2um+i um+3 v2. Then 2 2 each of um+i and um+3 joins to each of v4, v5,..., vn. For j = 1, 2,..., "], let Dj = um+iv4iv4i+1um+i. If n = 1 (mod 4), then n-- (= "n-2]) tubes T{, T2',..., T_1 are added to the present surface one by one such that u m+i v5 is re- 4 2 drawn on T1, and u m+i v4i and um+i v4i+1 are redrawn on T/ for i = 2, 3,..., . If n = 3 (mod 4), then ^ (= "1) tubes T{, T2,..., T^ are added to the 4 present surface one by one such that u m+i v4 is drawn on T{, and u m+i v4i+3 and um+i v4i are redrawn on T/ for i = 2, 3,..., nt-1. As in Case 1, there is a facial walk Wrn_2n which contains um_i, v4,..., vn and v2. Next, um_i joins to v, if I 4 I 2 2 J it appears once in W| | or a copy of v, if it appears more than once in W| ^, where v, is a vertex in v4, v5,..., vn and v2. Let n3 be the obtained embedding. Then it is an embedding on the surface of the genus m-3 + " n-2 ]. (4) In this step we proceed the similar argument as in (4) and (5) in Case 1. There are (m-34("-3) tubes being added to the present surface. The detail is omitted here. Let n4 be the obtained embedding. Then it is an embedding of Cm + Kn on the surface of genus m-3 + I"1 + (m-34("-3). Need to say that for the purpose that each of v1; v2 and v3 is connected with v4,..., vn, we need add at least 6(n-3)2 tubes. Since each of um_i, um+i and um+3 has been connected with each of v4,..., vn, 2 2 2 m is at least 3 + 6(n — 3) (= 6n — 15). D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 249 Since m = 3 (mod 4) and n = 1 (mod 2), we have that \ (m-2H"-2) 1 = ^ + \n-21 + (m-34(n-3). So n4 is an embedding of Cm + Kn on the surface of genus |- (m-2)(n-2) 1. n 4 An upper bound for 7 (Cm + Kn) if m is even In the section we shall study the orientable genus of Cm + Kn if m is even. Lemma 4.1. Suppose that m = 0 (mod 2). If m > 8, then m2 Y(Cm + K4) < Proof. We firstly construct an embedding on a sphere. Cm, v1, and v2 are placed in the sphere as in the proof of Lemma 3.1, and each of v1 and v2 joins to u1, u2,..., un. Let F1 = v1 u1u2v1 and F2 = v2w3w4v2. Next, the vertex v3 is placed in the interior of F and is connected with to u1, u2, and v1, and the vertex v4 is placed in the interior of F2 and is connected with u3, u4, and v2. At last, the tube T\ is added between the facial cycle v3u1u2v3 and the facial cycle v4u3u4v4. Then six edges are drawn on in the way shown in (1) of Figure 15. Figure 15: Two drawings of edges on or T2. Note that there are two edges connecting u2 and u3. Let F3 = v1w2u3v1 and F4 = v2u2u3v2. We now delete the edge u2u3 which is a common edge of F3 and F4. Then F3 and F4 are merged into a facial cycle F5 = v1u2v2u3v1. Next, the edge v1v2 is drawn in the interior of F5. Let F6 = u1 v3v4u1 (refer to (1) of Figure 15), and let F7 = v1m5m6v1. The tube T2 is now added between F6 and F7. Then the five edges are drawn on T2 in the way shown in (2) in Figure 15. Let F8 = w5v3v4w5 (refer to (2) of Figure 15), and let F9 = v2M8urv2. Then the tube T3 is added between F8 and F9. Next, the five edges v3u8, v3u7, v4u7, v4u8 and v4v2 are drawn on T3 in the similar way to that in (2) in Figure 15. Thus, v is connected with vj if i = j. If m = 8, there is nothing to do. If m > 8, let F = {F' | F' = W7V3V4W7}, and let Q = {Qi | Qi = V1U7+2iU8+2iV1, i = 1, 2,..., }. We apply the operation of adding m-8 tubes with respect to F and Q to realize an embedding of Cm + K4. Thus, there are + 3 (= ) tubes being used. Hence, y(Cm + K4) < \m-21. □ Lemma 4.2. Suppose that m = 0 (mod 2) and n = 0 (mod 2). If n > 6 and m > 4n - 4, then Y(Cm + K„) < (m - 2)(n - 2) 4 250 Ars Math. Contemp. 17 (2019) 223-253 Proof. We construct an embedding of Cm + Kn in the following steps. (1) The cycle Cm and vertices v1 ,v2 are placed in a sphere as in the proof of Lemma 3.1. Next, each of v1 and v2 joins to u1,u2,..., um. Let F1 = v1m1m2v1 and F2 = v1M3M4v1. The two vertices v4 and v6 are placed in the interior of F1, and each of u1 and u2 joins to each of v4 and v6 such that there are two facial 4-cycles F1 = u1v4u2v6u1 and F2' = v1w1v6M2v1. The two vertices v3 and v5 are placed in the interior of F2, and each of u3 and u4 joins to each of v3 and v5 such that there are two facial 4-cycle F3 = u3v3w4v5w3 and D[ = w3w4v5w3. The path P = v7v8 ... vn is placed in the interior of F2 such that v7 is near to v6. Next, each of u1 and u2 joins to each of v7,v8,..., vn. The obtained embedding is denoted by n1. (2) In the step each of u1, u2, u3 and u4 will be connected with each of v3, v4,..., vn, and v1 is connected with v2. For the above purpose, the tube T1 is firstly added between F1 and F3, and the five edges u1v5, u2v3, u3v4, u4v6 and u2u3 are drawn on T1 in the way shown in (1) of Figure 16. Thus, there are two edges connecting u2 and u3. The edge u2u3 which is the common edge of facial cycles v1m2m3v1 and v2u2u3v2 is deleted. Then there is a facial cycle F3 = v1u2v2u3v1. Next, v1 joins to v2 in the interior of F3. The tube T2 is now added between the facial cycles u1v4u3v5u1 and w2v3w4v6u2 (refer to (1) in Figure 16), and the six edges u1v3, u2v5, u3v6, u4v4, v3v4 and v5v6 are drawn on T2 in the way shown in (2) of Figure 16. U1 V4 U2 Vq Ui V4 U3 V5 U3 V3 U4 V5 (1) U2 V3 U4 Vq (2) Figure 16: Two drawings of edges on T1 or T2. For i = 1, 2,..., S-6, let D< = w2V2i+5V2i+6W2. Let D = {Di | i = 1,2,..., S-6} and V = {D'x}. We apply the operation of adding tubes with respect to D and V such that both u3 and u4 are connected with each of v7, v8,..., vn. By Lemma 2.11, there are n-6 tubes being used. Let n2 be the obtained embedding. (3) We proceed a similar argument to that in (3) in the proof of Lemma 3.2. We shall add (m—440-2) tubes to the present surface to realize an embedding n3 of Cm + Kn. The detail is omitted here. For the purpose that each of v1 and v2 joins to each of v3,..., vn, 2(2 )2 tubes will be used by Lemma 2.1. So m is at least 4 + 4 x n-2 (= 4n - 4). Obviously, n3 is an embedding of Cm + Kn on the surface of genus 2 + 6 + (m-44("-2). Since m = 0 (mod 2) and n = 0 (mod 2), we have that (m - 2)(n - 2) 2 + n — 6 + (m — 4)(n — 2) So Y (Cm + Kn) < r (m-2f-2) 1. □ 4 D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 251 Lemma 4.3. Suppose that m = 0 (mod 2) and n = 1 (mod 2). If m > 6n — 14 and n > 5, then Y(Cm + Kn) < (m — 2)(n — 2) 4 Proof. We proceed a similar argument to that in the proof of Lemma 3.3. (1) Let Pm = u1u2... um. Then Pm, v1, v2, and v3 are placed in a sphere as in (1) in the proof of Lemma 3.3. If m = 0 (mod 4), then each of v1 and v3 joins to each of u1,u2,..., um such that v1ui and v3ui are in the upper side and lower side of Pm, respectively. Next, each of v2 and v1 joins to each of u m+2, u m+4,... ,um such that 2 2 v2ui and v1ui are in the upper side and lower side of Pm, respectively. Also, v1 joins to v3. If m = 2 (mod 4), then each of v1 and v3 joins to each of u1, u2,..., um such that v1ui and v3ui are in the upper side and lower side of Pm, respectively. Next, each of v2 and v1 joins to each of u m+22, u m+4,... ,um such that v2ui and 22 v1ui are in the upper side and lower side of Pm, respectively. Also, v1 joins to v3, v2 joins to u m, and v3 joins to u m+2. Let n1 be the obtained embedding on the sphere. 2 2 (2) As in (2) in the proof of Lemma 3.3, there are m tubes being added to the sphere if m = 0 (mod 4), or there are m2 tubes being added to the sphere if m = 2 (mod 4), such that each of v2 and v3 is connected with all rest vertices in u1,u2,..., um. Also, u1 is connected with um, and v2 is connected with v3. Need to say that \ — 1 = f if m = 0 (mod 4), or \^1 = ^ if m = 2 (mod 4). Thus, there are \ f-21 tubes being used in the above procedure. Let P' = v4v5 ...vn. If m = 0 (mod 4), then P' is placed in the facial cycle v1u1u2v1, and each of u1 and u2 is connected with v4,v5,... ,vn. If m = 2 (mod 4), then P' is placed in the facial cycle v1umum+1v1, and each of um and um +1 is connected with v4, v5,..., vn. Let (3) Xo = {Qo,i I Qo,i = u2'U2i+2v2i+3u2, i = 1, 2,..., "^r-3} if m = 0 (mod 4), or Xo = {Qo,i I Qo,i = um v2i+2v2i+3um, i = 1, 2,..., n-} if m = 2 (mod 4). Let yo yo' {Ro,i {Ro ,i Ro R o,i v2u2i+1u2i'02, i = 1, 2, v3um+1-2ium+2-2iv3, n-3 2 }, and n-3 2 1, 2,..., }. We apply the operation of adding 2( "r-3)2 tubes starting from Xo, yo and y'0. Next procedures are similar to that in (4) in the proof of Lemma 3.3. Eventually, we obtain an embedding of Cm + Kn by adding (m--24n-3) tubes. Note that for the purpose that each of v1,v2 and v3 is connected with each of v4,v5,... ,vn, we need to add at least 3 x 2 x tubes by Lemma 2.10. Thus, m > 6(n — 3) + 2 + 2 = 6n — 14 if m = 0 (mod 4), or m > 6(n — 3) + 2 = 6n — 16 if m = 2 (mod 4). Since m = 0 (mod 2) and n = 1 (mod 2), \ (m-24(n-2) 1 = (m-2)(n-3) + \ 1. Since m = \^ 1 if m = 0 (mod 4), or —^ = \^ 1 if m = 2 (mod 4), the obtained embedding is an embedding of Cm + Kn on the surface of genus r (m-2)(n-2) \ 4 )1. □ 252 Ars Math. Contemp. 17 (2019) 223-253 5 Conclusions Lemma 5.1 ([10]). If m > 2 and n > 2, then Y (Km,„) (m - 2)(n - 2) 4 Considering that Km,n is a subgraph of Cm + Kn, Theorem 5.2 follows from Lemmas 3.1, 3.2, and 3.3, Lemmas 4.1,4.2, and 4.3, and Lemma 5.1. Theorem 5.2. Suppose that m and n are two integers. Then Y (Cm + Kn) = (m - 2)(n - 2) 4 if n > 4 and m, n satisfy one of the following conditions: (1) m = 1 (mod 2), n = 0 (mod 2), and m > 4n — 5, (2) m = 1 (mod 2), n = 1 (mod 2), and m > 6n — 13, (3) m = 0 (mod 2), n = 0 (mod 2), and m > 4n — 4, (4) m = 0 (mod 2), n = 1 (mod 2), and m > 6n — 14. Obviously, the maximal value in 4n — 5,4n — 4, 6n — 13 and 6n — 14 is 12 if n = 4, or 6n — 13 if n > 5. The result below follows from Lemma 5.1 and Theorem 5.2 directly. Corollary 5.3. Suppose that m and n are two integers. Let Gi be a spanning subgraph of Cm, and let G2 be a spanning subgraph of Kn. If n = 4 and m > 12, or n > 5 and m > 6n - 13, then Y (Gi + G2) (m - 2)(n - 2) 4 Since Kr,S,t (r > s > t > 3) is a spanning subgraph of Cr + KS+i, we have the following result by Theorem 5.2. Corollary 5.4. If r > s > t > 3 and r > 6(s +1) — 13, then Y(Kr,s,t) = (r - 2)(s +1 - 2) 4 Therefore, Stahl and White's conjecture ([12]) on the orientable genus of the complete tripartite graph KrjSji holds if r > s > t > 3 and r > 6(s +1) - 13. References [1] J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer, New York, 2008, doi:10.1007/978-1-84628-970-5. [2] D. L. Craft, Surgical Techniques for Constructing Minimal Orientable Imbeddings of Joins and Compositions of Graphs, Ph.D. thesis, Western Michigan University, 1991, https:// search.proquest.com/docview/303919820. [3] D. L. Craft, On the genus of joins and compositions of graphs, Discrete Math. 178 (1998), 25-50, doi:10.1016/s0012-365x(97)81815-8. D. Ma and H. Ren: The orientable genus of the join of a cycle and a complete graph 253 [4] G. A. Dirac, The coloring of maps, J. London Math. Soc. 28 (1953), 476-480, doi:10.1112/ jlms/s1-28.4.476. [5] M. N. Ellingham and D. C. Stephens, The orientable genus of some joins of complete graphs with large edgeless graphs, Discrete Math. 309 (2009), 1190-1198, doi:10.1016/j.disc.2007. 12.098. [6] T. Gallai, Kritische Graphen I, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 8 (1963), 165-192. [7] T. Gallai, Kritische Graphen II, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 8 (1963), 373-395. [8] V. P. Korzhik, Triangular embeddings of Kn — Km with unboundedly large m, Discrete Math. 190 (1998), 149-162, doi:10.1016/s0012-365x(98)00040-5. [9] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, Maryland, 2001. [10] G. Ringel, Das Geschlecht des vollständigen paaren Graphen, Abh. Math. Sem. Univ. Hamburg 28 (1965), 139-150, doi:10.1007/bf02993245. [11] G. Ringel, Map Color Theorem, volume 209 of Die Grundlehren der mathematischen Wissenschaften, Springer-Verlag, Heidelberg, 1974, doi:10.1007/978-3-642-65759-7. [12] S. Stahl and A. T. White, Genus embeddings for some complete tripartite graphs, Discrete Math. 14 (1976), 279-296, doi:10.1016/0012-365x(76)90042-x. [13] C. Thomassen, Color-critical graphs on a fixed surface, J. Comb. Theory Ser. B 70 (1997), 67-100, doi:10.1006/jctb.1996.1722. [14] A. T. White, Graphs, Groups and Surfaces, volume 8 of North-Holland Mathematics Studies, North-Holland, Amsterdam, 1973, doi:10.1016/s0304-0208(08)x7063-x.