- Email: [email protected]

Journal of Combinatorial Theory, Series B 91 (2004) 253–287 http://www.elsevier.com/locate/jctb

Exponential families of nonisomorphic nonorientable genus embeddings of complete graphs$ Vladimir P. Korzhika and Heinz-Ju¨rgen Vossb b

a Bogomoltsa 3/5, Chernovtsy 58001, Ukraine Technische Universita¨t Dresden, Fachrichtung Mathematik, Mommsenstr. 13, D-01062 Dresden, Germany

Received 17 July 2002

Abstract It is shown that there are constants M and c such that for nXM the number of nonisomorphic nonorientable genus embeddings of the complete graph Kn is at least c2n=6 : r 2004 Elsevier Inc. All rights reserved. Keywords: Topological embedding; Genus embedding; Nonisomorphic embeddings; Complete graph

1. Introduction The nonorientable genus of a graph is the smallest q such that the graph can be embedded in Nq ; the sphere with q crosscaps attached; any such embedding is called a nonorientable genus embedding (NG-embedding, for short) of the graph. In the course of the proof of the Map Color Theorem [10] one NG-embedding was constructed for every complete graph. There arose the natural question of what is the rate of growth of the number of nonisomorphic NG-embeddings of Kn ? It is known that only for n 0; 1 mod 3 the NG-embeddings of Kn are triangular. Until recently, there were surprisingly few results [1,2,4] about the number of nonisomorphic NG-embeddings of complete graphs, and all the results are related to triangular NG-embeddings. Only in the last few years was it shown [3,5], that there is $ The results of this paper were obtained while the ﬁrst author visited Technical University of Dresden. This visit was sponsored by the German Academic Exchange Service (DAAD), Grant A/01/06010. E-mail address: [email protected] (V.P. Korzhik).

0095-8956/$ - see front matter r 2004 Elsevier Inc. All rights reserved. doi:10.1016/j.jctb.2004.02.002

ARTICLE IN PRESS 254

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

a great number of nonisomorphic triangular NG-embeddings of some complete graphs Kn : In the present paper we consider the problem of construction of exponentially many (in n) nonisomorphic NG-embeddings of complete graphs Kn : Now there are two approaches to solve the problem. The ﬁrst approach [3,5] uses recursive constructions and a cut-and-paste 2 technique. This approach establishes the existence of at least 2an OðnÞ nonisomorphic orientable (resp. nonorientable) triangular embeddings of Kn for some families of n such that n 3 or 7 mod 12 (resp. n 1 or 3 mod 6). This approach has some restrictions: using recursive constructions does not make it possible to obtain the 2 2an OðnÞ lower bound for all values of n 3 or 7 mod 12 in the orientable case and n 1 or 3 mod 6 in the nonorientable case. The second approach [8,9] uses the current graph technique. This approach gives only 2bnh lower bound on the number of nonisomorphic orientable genus embeddings of Kn ; but the approach applies to the larger range of cases n modulo 12 and, in contrast to the ﬁrst approach, yields families of nonisomorphic nontriangular genus embeddings as well as nonisomorphic triangular ones. Papers [8,9] give at least 2bnh nonisomorphic orientable genus embeddings of Kn for nc0; 3 mod 12: In the present paper the theory given in [8] is generalized to the nonorientable case. In Section 2 we consider those 2-cell embeddings of a complete graph Kn which are generated by schemes on an abelian group F of order n: By a scheme on F we mean a pair ½P; L; where P is a cyclic permutation ðb1 ; b2 ; y; bn1 Þ of all nonzero elements of F (P determines a rotation of Kn ) and L is a set of nonzero elements of F such that if dAL; then dAL and da d (L determines the set of twisted edges of Kn ). Consider the embeddings generated by schemes ½ðb1 ; b2 ; y; bn1 Þ; L and ½ðg1 ; g2 ; y; gn1 Þ; L0 : We show (Theorem 1) that if (a) or (b) holds: (a) jFj is odd, (b) jFj is even and either jLj þ jL0 joð1=2ÞjFj or jLj þ jL0 jXð3=2ÞjFj; then these two embeddings are isomorphic if and only if there is an automorphism j of F such that L0 ¼ ffðdÞ : dALg and ðg1 ; g2 ; y; gn1 Þ is either ðjðb1 Þ; jðb2 Þ; y; jðbn1 ÞÞ or ðjðbn1 Þ; y; jðb2 Þ; jðb1 ÞÞ: Each scheme on F can be represented by an index one current graph (cascade) with the current group F: A relation of isomorphism is deﬁned on the set of all cascades with the current group F: It is shown (Theorem 2) that two schemes are equivalent if and only if the cascades determining the schemes are isomorphic. In Section 3 we prove Theorem 3 that gives us a method of construction of families of nonisomorphic embeddings of complete graphs. This method and cascades from paper [7] are used in Section 4 to show that for every integer 0pip11; there are integers hðiÞp9 and mðiÞp9 such that the complete graph K12sþi for sXmðiÞ has at least 22shðiÞ nonisomorphic genus embeddings.

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

255

2. Cascades and isomorphism In what follows by an embedding of a graph, we mean a 2-cell embedding of the graph in a surface. In this section we ﬁrst give some preliminaries. Then we consider the embeddings of complete graphs which are generated by schemes. Theorem 1 gives some conditions under which the following holds: the embeddings of a complete graph generated by two schemes are isomorphic if and only if the schemes are equivalent. Then we show (Theorem 2) that two schemes are equivalent if and only if the cascades determining the schemes are isomorphic. The reader is referred to [6,10] for more detailed exposition of the theory of current graphs. We assume the reader to be familiar with current graphs, the log of a circuit, derived graphs and their derived embeddings generated by the current graphs. Digraphs considered in this paper may have loops and multiple arcs. Permutations are expressed in cyclic form: ðd1 ; d2 ; y; dm Þ: Let G be a connected digraph with the vertex set V ðGÞ and the arc set AðGÞ with an involutary permutation y of AðGÞ called the involution of G such that if an arc a is directed from the vertex v to the vertex w; then the arc ya is directed from w to v; the arcs a and ya are called reverse arcs. An arc a such that a ¼ ya is called a self-reverse loop. An arc directed from the vertex v to the vertex w is denoted by ½v; w: A rotation D of G is a permutation of AðGÞ whose orbits cyclically permute the arcs directed from each vertex. The rotation D can be represented as D ¼ fDu : uAV ðGÞg; where Du ; called the rotation of the vertex u; is a cyclic permutation of the arcs directed from u: In what follows, every digraph under consideration is automatically associated with the natural arc-reversing involution. We will consider triples /G; W ; DS; where W is a subset of AðGÞ such that if aAW ; then aaya and yaAW : The arcs belonging (resp. not belonging) to W are called the type 1 (resp. type 0) arcs. The pair W ; D determines oriented cycles in G called circuits. The circuits are constructed by the following well-known trace procedure [6,10]. If a ¼ ½v; w is an arc of a circuit, then the subsequent arc of the circuit is uniquely determined by Dw ; by the type of the arc a and by the behavior with which the circuit traverses the ﬁrst half of the arc a: The circuit has two modes of behavior, normal and alternative. In normal behavior the circuit obeys the rotation given at each vertex. In alternative behavior the circuit acts as if the given rotations are reversed. When the circuit traverses a type 1 arc, its behavior switches modes at the midpoint of the arc. If ða1 ; a2 ; y; am Þ is a circuit for W ; D; then ðyam ; y; ya2 ; ya1 Þ is a circuit for W ; D too, the two circuits are called reverse circuits. The set of all circuits for W ; D is partitioned into pairs of reverse circuits. A rotation D of G is called a one-rotation for /G; W S if the pair W ;D determines exactly two circuits, the circuits being reverse. Given a triple /G; W ; DS and a vertex v of G; the switch operation at v is deﬁned as follows: reverse the rotation of v and change the type of arcs that are incident with v and are not loops. Two triples are switch equivalent if one of the triples can be obtained from the other by switch operations. If /G; W ; DS and /G; W 0 ; D0 S are switch equivalent, then the two pairs W ; D and W 0 ; D0 determine the same circuits.

ARTICLE IN PRESS 256

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

In a ﬁgure of G; a circuit ða1 ; a2 ; y; am Þ can be depicted as an oriented cycle, called the d-cycle of the circuit, passing near the arcs a1 ; a2 ; y; am in this order; this cycle is depicted as a solid (resp. dashed) line when it has normal (resp. alternative) behavior. We will speak about pieces of the d-cycle; pieces can include other pieces; some pieces are solid, other pieces are dashed; the d-cycle consists of alternating solid and dashed pieces, etc. Given a connected nonoriented graph K; the associated digraph K% is deﬁned in the following way. A directed edge of K is an edge endowed with one of the two possible directions. Every edge of K gives rise to two oppositely directed edges, called reverse % and these arcs for all edges of K form the arc set AðKÞ: % arcs of K; The boundary of a face of an embedding of a graph K is a closed walk in K called the boundary cycle of the face. Combinatorially, by the face set of the embedding we mean the set of boundary cycles of the faces of the embedding. The boundary cycle of a face has two opposite directions, the boundary cycle with a chosen direction is called a directed boundary cycle of the face and is considered to be an oriented closed % Ringel [11] has shown that every triple /K; % W ; DS generates an walk of K: embedding of K such that the circuits determined by W ; D are exactly the directed boundary cycles of the faces of the embedding, and that every embedding of K is % W ; DS: generated by some triple /K; Let K be a graph without loops and multiple edges. A face of an embedding of K will be designated as a cyclic sequence ½v1 ; v2 ; y; vm of vertices (for convenience, we enclose the sequence in brackets) obtained by listing the incident vertices when traversing the boundary cycle of the face in some chosen direction. The sequences ½v1 ; v2 ; y; vm and ½vm ; y; v2 ; v1 designate the same face. We can differentiate embeddings of K as labeled objects (in this case we speak about different embeddings, they have different face sets) and as unlabeled objects (in this case we speak about nonisomorphic embeddings). Two embeddings f and f 0 of a graph K in a surface are isomorphic if there is an automorphism c of K such that if ½v1 ; v2 ; y; vm is a face of f ; then ½cðv1 Þ; cðv2 Þ; y; cðvm Þ is a face of f 0 : The automorphism c is called an isomorphism of the embedding f onto the embedding f 0 : Note, that for a complete graph every bijection between the vertices is an automorphism of the graph. % W ; DS generating the Given an embedding of the graph K; every triple /K; embedding can be constructed in the following way. Arbitrarily ﬁx an orientation at every vertex of the embedded graph K: This collection of local orientations determines a rotation D of K% where the rotation of a vertex is induced by the orientation at the vertex. Deﬁne an arc of K% to be of type 0 if and only if the orientations at the vertices incident with the arc agree. As a result, we obtain a triple % W ; DS generating the embedding. Reversing the orientation at a vertex v of the /K; % W 0 ; D0 S obtained from /K; % W ; DS by embedded graph K yields the triple /K; % W ; DS and all triples switch equivalent to switch operation at v: Hence the triple /K; % W ; DS are all triples generating the embedding. /K; % W ; DS we To study the isomorphism of embeddings of K generated by triples /K; need some deﬁnitions.

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

257

Two digraphs G and G0 with the involutions y and y0 ; respectively, are isomorphic if there are bijections o : V ðGÞ-V ðG 0 Þ and o % : AðGÞ-AðG 0 Þ such that if an arbitrary arc a of G is directed from a vertex v to a vertex w; then the arc oðaÞ is % directed from the vertex oðvÞ to the vertex oðwÞ; and oðyaÞ ¼ y0 oðaÞ: % % The pair ðo; oÞ % is called an isomorphism of G onto G0 : An isomorphism of G onto itself is called an automorphism of the digraph. % W ; DS and /K; % W 0 ; D0 S are isomorphic if there is an automorphism Triples /K; % the arcs a and oðaÞ ðo; oÞ have the same type, % of K% such that for every arc a of K; % % and for every vertex v of K; if Dv ¼ ða1 ; a2 ; y; am Þ; then DoðvÞ 0 ¼ % W ; DS ðoða % 1 Þ; oða % 2 Þ; y; oða % m ÞÞ: The pair ðo; oÞ % is called an isomorphism of /K; % W 0 ; D0 S: Clearly, if ðb1 ; b2 ; y; bh Þ is a circuit determined by W ; D; then onto /K; ðoðb % 1 Þ; oðb % 2 Þ; y; oðb % h ÞÞ is a circuit determined by W 0 ; D0 ; hence, isomorphic triples % W ; DS and /K; % W 0 ; D0 S generate isomorphic embeddings. /K; % W ; DS and Claim 1. The embeddings f and f 0 of a graph K generated by triples /K; 0 0 % % /K; W ; D S are isomorphic if and only if /K; W ; DS is isomorphic to a triple e;D eS switch equivalent to /K; % W % W 0 ; D0 S: /K; e;D eS be isomorphic, and /K; e;D eS and % W ; DS and /K; % W % W Proof. Let /K; 0 0 % /K; W ; D S be switch equivalent. The isomorphic triples generate isomorphic embeddings, and the switch equivalent triples generate the same embedding. Hence, the embeddings f and f 0 are isomorphic. For the sufﬁciency, let c be an isomorphism of f onto f 0 : Deﬁne an automorphism ðo; oÞ wÞ ¼ ½cðuÞ; cðwÞ for % of K% as follows: oðvÞ ¼ cðvÞ for every vertex v; oð½u; % e ¼ fwð½u; every arc ½u; w: Now deﬁne: W wÞ : ½u; wAW g; for every vertex v; if Dv ¼ % eoðvÞ ¼ ðoða ða1 ; a2 ; y; am Þ; then D % 1 Þ; oða % 2 Þ; y; oða % m ÞÞ: We obtain a triple e e % % /K; W ; DS isomorphic to /K; W ; DS: We have that ½v1 ; v2 ; y; vh is a face of f e;D eS: % W iff ½cðv1 Þ; cðv2 Þ; y; cðvh Þ is a face of the embedding generated by /K; e;D eS and /K; % W % W 0 ; D0 S generate the same embedding f 0 ; thus the Hence, /K; triples are switch equivalent. & Let F be an abelian group of order n: The group operation is written additively and the element of F inverse to an element d is written as d: Denote by Kn the complete graph with the vertex set F and the arc set f½x; x þ d : xAF; dAF\f0gg with the involution y½x; x þ d ¼ ½x þ d; x: By a scheme on F we mean a pair ½P; L; where P is a cyclic permutation ðb1 ; b2 ; y; bn1 Þ of all nonzero elements of F; and L is a subset of nonzero elements of F such that if dAL; then dAL and da d: The scheme ½P; L determines a triple /K% n ; W ; DS as follows: ½x; x þ dAW iff dAL; Dx ¼ ð½x; x þ b1 ; ½x; x þ b2 ; y; ½x; x þ bn1 Þ for every vertex xAF: The embedding of Kn generated by the triple is said to be generated by the scheme ½P; L also. It is easy to see that if ½v1 ; v2 ; y; vh is a face of the

ARTICLE IN PRESS 258

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

embedding, then ½v1 þ D; v2 þ D; y; vh þ D is a face of the embedding for every DAF too. This observation leads to the following claim. Claim 2. Let two schemes on F generate embeddings f and f 0 ; respectively, of Kn : If the embeddings are isomorphic, then there is an isomorphism c of f onto f 0 such that cð0Þ ¼ 0: % % Proof. Let c% be an isomorphism of f onto f 0 : If we deﬁne cðxÞ ¼ cðxÞ cð0Þ for every vertex xAF; then c is an isomorphism of f onto f 0 also. & Given a set L of elements of F and a cyclic permutation P ¼ ðd1 ; d2 ; y; dn1 Þ of F\f0g; for an automorphism j of F denote jðLÞ ¼ fjðxÞ : xALg and jðPÞ ¼ ðjðd1 Þ; jðd2 Þ; y; jðdn1 ÞÞ: Two schemes ½P; L and ½P0 ; L0 on F are equivalent if there is an automorphism j of F such that L0 ¼ jðLÞ and either P0 ¼ jðPÞ or P0 ¼ jðP1 Þ: This deﬁnition of equivalent schemes is motivated by the fact that triples /K% n ; W ; DS and /K% n ; W ; D1 S; being switch equivalent, generate the same embedding. Theorem 1. Let schemes ½P; L and ½P0 ; L0 on F generate embeddings f and f 0 ; respectively. Suppose that (a) or (b) holds: (a) jFj is odd, (b) jFj is even and either jLj þ jL0 joð1=2ÞjFj or jLj þ jL0 jXð3=2ÞjFj; Then the embeddings are isomorphic if and only if the schemes are equivalent. Proof. Let the schemes ½P; L and ½P0 ; L0 determine the triples /K% n ; W ; DS and /K% n ; W 0 ; D0 S; respectively. Suppose that L0 ¼ jðLÞ and either P0 ¼ jðPÞ or P0 ¼ jðP1 Þ for an automorphism j of F: It is easily veriﬁed that if ½v1 ; v2 ; y; vh is a face of the embedding generated by /K% n ; W ; DS; then ½jðv1 Þ; jðv2 Þ; y; jðvh Þ is a face of the embedding generated by /K% n ; W 0 ; D0 S; hence, j is an isomorphism of f onto f 0 : For the sufﬁciency, suppose that f and f 0 are isomorphic. Then, by Claim 2, there is an isomorphism c of f onto f 0 such that cð0Þ ¼ 0: By Claim 1, the e;D eS switch equivalent to triple /K% n ; W ; DS is isomorphic to a triple /K% n ; W /K% n ; W 0 ; D0 S; and the isomorphism c determines the isomorphism ðo; oÞ % of e e /K% n ; W ; DS onto /K% n ; W ; DS such that: oðvÞ ¼ cðvÞ for every vertex v; oð½u; wÞ ¼ ½cðuÞ; cðwÞ for every arc ½u; w: % e;D eS is either /K% n ; W 0 ; D0 S or Lemma 1. If (a) or (b) holds, then /K% n ; W 1 0 0 /K% n ; W ; ðD Þ S: Proof. Suppose (reductio ad absurdum) that there is a partition V ðK% n Þ ¼ V1 ,V2 ; e;D eS is obtained from /K% n ; W 0 ; D0 S by switch where V1 ; V2 a|; such that /K% n ; W

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

259

operations at all vertices of V2 : Every vertex of K% n is the initial vertex of exactly e j ¼ jLj arcs from W e ; and of exactly jW 0 j ¼ jL0 j arcs from W 0 : For every arc a jW e iff aeW 0 : If a directed from a vertex of Vi to a vertex of Vj ; iaj; we have: aAW e and vertex vAVi ; iAf1; 2g; is the initial vertex of exactly mi arcs a such that aAW 0 aAW ; then we have jLj þ jL0 j 2mi ¼ jVj j;

ð1Þ

where jai: Since jLj and jL0 j are even, we get that jVj j is even for every j ¼ 0; 1; hence jV1 j þ jV2 j ¼ jFj is even, a contradiction in case (a). From (1) it follows that 2ðjLj þ jL0 jÞ ¼ jFj þ 2m1 þ 2m2 ;

ð2Þ

and since 0pmi ojVi j for every i ¼ 1; 2; we get from (1) and (2) that jFjp2ðjLj þ jL0 jÞo3jFj; a contradiction in case (b). & e;D eS is /K% n ; W 0 ; D0 S; then D e ¼ D0 ; that is Let P ¼ ðb1 ; b2 ; y; bn1 Þ: If /K% n ; W ðcðx þ b1 Þ cðxÞ; cðx þ b2 Þ cðxÞ; y; cðx þ bn1 Þ cðxÞÞ ¼ P0 ¼ ðcðb1 Þ; cðb2 Þ; y; cðbn1 ÞÞ

ð3Þ

e;D eS is /K% n ; W 0 ; ðD0 Þ1 S; then D e ¼ ðD0 Þ1 ; that is for every vertex xAF: If /K% n ; W ðcðx þ b1 Þ cðxÞ; cðx þ b2 Þ cðxÞ; y; cðx þ bn1 Þ cðxÞÞ ¼ ðP0 Þ1 ¼ ðcðb1 Þ; cðb2 Þ; y; cðbn1 ÞÞ

ð4Þ

for every vertex xAF: Lemma 2. Let c be a bijection between elements of F such that cð0Þ ¼ 0: Let ðb1 ; b2 ; y; bn1 Þ be a cyclic permutation of F\f0g: If ðcðx þ b1 Þ cðxÞ; cðx þ b2 Þ cðxÞ; y; cðx þ bn1 Þ cðxÞÞ ¼ ðcðb1 Þ; cðb2 Þ; y; cðbn1 ÞÞ

ð5Þ

for all xAF; then c is an automorphism of F: Proof. Since x in (5) takes n different values, we have that for some y; zAF; where yaz; the equality cðbi þ yÞ cðyÞ ¼ cðbi þ zÞ cðzÞ holds for all i ¼ 1; 2; y; n 1: This implies cðbi þ z þ dÞ ¼ cðbi þ zÞ þ D for i ¼ 1; 2; y; n 1; where fb1 ; b2 ; y; bn1 g ¼ F\f0g; we have cðx þ dÞ ¼ cðxÞ þ D

d ¼ y za0; D ¼ cðyÞ cðzÞa0:

Since

ARTICLE IN PRESS 260

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

for every xAF\fzg: The mapping c is a bijection and cðzÞ þ DefcðxÞ þ D : xAF\fzgg ¼ fcðx þ dÞ : xAF\fzgg; so cðz þ dÞ ¼ cðzÞ þ D and we get that cðx þ dÞ cðxÞ ¼ D ¼ cðdÞ for every xAF: We have d ¼ bi for some iAf1; 2; y; n 1g; whence cðbi þ xÞ cðxÞ ¼ D ¼ cðbi Þ

ð6Þ

for every xAF: From (5) and (6) it follows that cðbj þ xÞ cðxÞ ¼ D ¼ cðbj Þ

ð7Þ

for j ¼ 1; 2; y; n 1 and for all xAF: Since bj takes all values from F\f0g; we get from (7) that cðx þ yÞ ¼ cðxÞ þ cðyÞ for all x; yAF: Hence, c is an automorphism of F:

&

We have that c is an automorphism of F and, by (3) and (4), we obtain that P0 is e ¼ W 0 ; we have that cðx þ dÞ cðxÞ ¼ cðdÞAL0 iff either cðPÞ or cðP1 Þ: Since W dAL; hence L0 ¼ cðLÞ; that is, the schemes ½P; L and ½P0 ; L0 are equivalent. This completes the proof of the theorem. & Now we introduce cascades determining schemes on F: Denote by RðFÞ the set of all pairs /G; ZS; where G is a connected digraph, G has exactly n 1 arcs and has as many self-reverse loops as F has nonzero elements of order 2, and Z : AðGÞ-F\f0g such that: (i) for every element dAF\f0g of order 2, there is exactly one arc a of G such that ZðaÞ ¼ d; the arc is a self-reverse loop; (ii) for every pair fd; dg of reverse elements of F; there are exactly two arcs a1 ; a2 of G such that Zða1 Þ; Zða2 ÞAfd; dg; the arcs are reverse. The element ZðaÞ is called the current of the arc a: Given /G; ZSARðFÞ; where G has the involution y; deﬁne the subset W ðZÞDAðGÞ as follows: aAW ðZÞ iff ZðaÞ ¼ ZðyaÞ and aaya: A cascade with the current group F is a triple ½G; Z; D; where /G; ZSARðFÞ and D is a one-rotation for /G; W ðZÞS: The cascade determines a scheme ½P; L on F in the following way. Choose one of the two circuits determined by the pair W ðZÞ; D: Then the log of the circuit is P: The set L consists of all pairs fd; dgAF such that the circuit traverses an arc with current d twice in the same direction. Note that a cascade determines exactly two schemes (depending on the choice of the circuit), ½P; L and ½P1 ; L; these schemes are equivalent. Pairs /G; ZS; /G 0 ; Z0 SARðFÞ are said to be isomorphic if there is an isomorphism ðo; oÞ % of G onto G 0 ; and an automorphism j of F such that for every vertex v

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

261

of G; either Z0 oðaÞ ¼ jZðaÞ % for all arcs a directed from v; or ¼ jZðaÞ Z0 oðaÞ % for all arcs a directed from v: This pair ðo; oÞ % is called an isomorphism of /G; ZS onto /G 0 ; Z0 S; and the automorphism j is said to be associated with the isomorphism. An isomorphism of /G; ZS onto itself is called an automorphism of /G; ZS: Two cascades ½G; Z; D and ½G 0 ; Z0 ; D0 are isomorphic if there is an isomorphism ðo; oÞ % of /G; ZS onto /G 0 ; Z0 S with an associated automorphism j of F such that for every vertex v of G; if Dv ¼ ða1 ; a2 ; y; am Þ and Z0 oðaÞ ¼ jZðaÞ (resp. ¼ jZðaÞÞ % for all arcs a directed from v; then DoðvÞ 0 ¼ ðoða % 1 Þ; oða % 2 Þ; y; oða % m ÞÞ (resp. ¼ ðoða ¼ jZðaÞ for all arcs a of G (and, hence, if % m Þ; y; oða % 2 Þ; oða % 1 ÞÞ). If Z0 oðaÞ % Dv ¼ ða1 ; a2 ; y; am Þ; then DoðvÞ 0 ¼ ðoða % 1 Þ; oða % 2 Þ; y; oða % m ÞÞ for every vertex v of G), then the cascades are said to be strong isomorphic. This pair ðo; oÞ % is called an isomorphism or, respectively, a strong isomorphism of the cascade ½G; Z; D onto the cascade ½G 0 ; Z0 ; D0 and the automorphism j of F is said to be associated with this isomorphism. Given a cascade ½G; Z; D and a vertex v of G; the switch operation at v is deﬁned as follows: reverse the rotation of v and invert the currents on all arcs directed from v: Two cascades are called switch equivalent if one of the cascades can be obtained from the other by switch operations. We see that two cascades ½G; Z; D and ½G 0 ; Z0 ; D0 are e isomorphic iff the cascade ½G; Z; D is strongly isomorphic to a cascade ½G 0 ; Z* ; D 0 0 0 switch equivalent to ½G ; Z ; D : b the graph obtained from G by replacing every pair For a digraph G; denote by G of reverse arcs by an edge. Now we show that every scheme ½P; L on F is determined by a cascade with the current group F and we describe the set of all cascades determining the scheme. Let P ¼ ðd1 ; d2 ; y; dn1 Þ: Take an ðn 1Þ-gonal face whose boundary is an oriented cycle ða1 ; a2 ; y; an1 Þ consisting of n 1 arcs a1 ; a2 ; y; an1 : We construct a cascade ½G; Z; D such that: a1 ; a2 ; y; an1 are arcs of G; ða1 ; a2 ; y; an1 Þ is a circuit of the cascade such that when the circuit traverses the arc ai ; the current di is recorded in the log, i ¼ 1; 2; y; n 1: Consider the ðn 1Þ-gonal face as a symbolic representation of a surface with boundary: for every pair ai ; aj of arcs such that di ¼ dj ; we set ai ¼ aj (resp. ai ¼ a1 j ) if di AL (resp. di eL). After identifying the pairs of arcs we b in the surface with holes such that every hole is obtain an embedding of the graph G bounded by a self-reverse loop (an arc ai such that di is of order 2). Now, arbitrarily b: The collection of ﬁx an orientation at every vertex of the embedded graph G b: Clearly, orientations determines a triple /G; W ; DS generating the embedding of G 0 0 ða1 ; a2 ; y; an1 Þ is a circuit for W ; D: Every other triple /G; W ; D S generating the b is switch equivalent to /G; W ; DS: Let y be the involution of G: embedding of G

ARTICLE IN PRESS 262

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

Now we assign currents ZðaÞ to the arcs a of G such that when the circuit traverses the arc ai ; the current di is recorded in the log. The assignment is unique and is performed in the following way: if the arc ai is traversed with normal (resp. alternative) behaviour, then Zðai Þ ¼ di (resp. ¼ di ); if an arc a is not traversed by the circuit, then the arc ya is traversed, and we put ZðaÞ ¼ ZðyaÞ (resp. ¼ ZðyaÞ) if the arc a has type 1 (resp. 0). One can easily verify that the assignment is well deﬁned, /G; ZSARðFÞ and that we obtain a cascade ½G; Z; D such that W ¼ W ðZÞ and the cascade determines the scheme ½P; L: If we reverse the orientation at a vertex v of the b; then assigning the currents yields the cascade ½G; Z0 ; D0 obtained embedded graph G from ½G; Z; D by switch operation at v: Now we see that given a scheme ½P; L; the b is determined uniquely (up to isomorphism) and that the cascade embedded graph G ½G; Z; D and all the cascades switch equivalent to ½G; Z; D are all the cascades determining the scheme. As a consequence, we have the following claim. Claim 3. If two cascades G1 and G2 determine the same scheme on F; then there exists an isomorphism of G1 onto G2 with the associated trivial automorphism (the identity mapping) of F: Theorem 2. Two schemes ½P; L and ½P0 ; L0 on F are equivalent if and only if cascades G and G0 ; respectively, determining the schemes are isomorphic. % Hence, % L % and ½ðPÞ % 1 ; L: Proof. Every cascade determines exactly two schemes, ½P; to prove the theorem, it sufﬁces to prove (a): (a) Cascades G and G0 are isomorphic iff they determine schemes ½P; L and ½jðPÞ; jðLÞ; respectively, where j is an automorphism of F: Now we prove (a). Suppose that G and G0 determine ½P; L and ½jðPÞ; jðLÞ; respectively. It sufﬁces to prove (b): % and G % 0; (b) ½P; L and ½jðPÞ; jðLÞ are determined by strong isomorphic cascades G respectively. % 0 ) are isomorphic, hence, Then, by Claim 3, it follows that G and G% (resp. G0 and G 0 G and G are isomorphic. Now we prove (b). Let P ¼ ðd1 ; d2 ; y; dn1 Þ: We will follow the above described procedure of constructing cascades determining a given scheme. Take two ðn 1Þgonal faces whose boundaries are oriented cycles ða1 ; a2 ; y; an1 Þ and ðb1 ; b2 ; y; bn1 Þ; respectively. Consider the faces as symbolic representations of a surface with boundary: for every pair of arcs ai and aj such that di ¼ dj ; we set ai ¼ aj (resp. ai ¼ a1 j ) if di AL (resp. di eL); for every pair of arcs bi and bj such that jðdi Þ ¼ jðdj Þ; we set bi ¼ bj (resp. bi ¼ b1 j ) if jðdi ÞAjðLÞ (resp. jðdi ÞejðLÞ). b and Gb0 in a After identifying the pairs of arcs, we obtain embeddings of graphs G 0 surface. Clearly, there is an isomorphism ðo; oÞ % of G onto G such that oða % i Þ ¼ bi for every i ¼ 1; 2; y; n 1: Construct a triple /G; W ; DS generating the embedding of G and then assign the currents ZðaÞ to the arcs a of G such that we obtain the cascade

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

263

½G; Z; D where W ¼ W ðZÞ and the circuit ða1 ; a2 ; y; an1 Þ has the log P (the current di is recorded in the log when the circuit traverses the arc ai ). Now deﬁne a triple /G0 ; W 0 ; D0 S as follows: W 0 ¼ fwðaÞ : aAW g; if Dv ¼ ðc1 ; c2 ; y; cm Þ; then DoðvÞ 0 ¼ % ðoðc % 1 Þ; oðc % 2 Þ; y; oðc % m ÞÞ for every vertex v of G: The triple /G 0 ; W 0 ; D0 S generates the embedding of G 0 and the pair ðo; oÞ % is an isomorphism of /G; W ; DS onto /G0 ; W 0 ; D0 S: Assign the currents Z0 ðbÞ to the arcs b of G 0 such that we obtain the cascade ½G 0 ; Z0 ; D0 where W 0 ¼ W ðZ0 Þ and the circuit ðb1 ; b2 ; y; bn1 Þ has the log ZðPÞ (the current Zðdi Þ is recorded in the log when the circuit traverses the arc bi ). Now we have that ðo; oÞ % is an isomorphism of ½G; Z; D onto ½G 0 ; Z0 ; D0 such that 0 Z ðwðaÞÞ ¼ jðZðaÞÞ for every arc a of G; that is, ðo; oÞ % is a strong isomorphism. % For the sufﬁciency, suppose that G and G0 are isomorphic. Then G and G0 are % and G % 0 ; respectively. It remains to show isomorphic to strong isomorphic cascades G % 0 with an associated automorphism that if ðo; oÞ % is a strong isomorphism of G% onto G 0 % % j of F; then the cascades G and G determine schemes ½P; L and ½jðPÞ; jðLÞ; respectively. Now it is easy to see that if C ¼ ða1 ; a2 ; y; an1 Þ is a circuit of G% with % 0 with the log ðd1 ; d2 ; y; dn1 Þ; then C 0 ¼ ðoða % 1 Þ; oða % 2 Þ; y; oða % n1 ÞÞ is a circuit of G the log ðjðd1 Þ; jðd2 Þ; y; jðdn1 ÞÞ; and the circuit C traverses an arc a with current d twice in the same direction iff the circuit C 0 traverses the arc oðaÞ with current jðdÞ % twice in the same direction. Hence, G% and G% 0 determine schemes ½P; L and ½jðPÞ; jðLÞ; respectively. This completes the proof of the theorem. &

3. Generating nonisomorphic embeddings In this section we prove Theorem 3 that gives a method of construction of families of nonisomorphic cascades. Then we describe cascades that will be used in Section 4 and give all material to facilitate construction checking in Section 4. To prove Theorem 3 we need Lemma 3. Given an automorphism j of F; denote by j the automorphism of F which is deﬁned as ðjÞðxÞ ¼ jðxÞ for all xAF: Lemma 3. Suppose that there is an automorphism ðo; oÞ % of /G; ZSAF with an associated automorphism j of F: Then j and ðjÞ are all automorphisms of F associated with ðo; oÞ: % Proof. Since jðZðaÞÞ ¼ ðjÞðZðaÞÞ; we see that j is associated with ðo; oÞ % too. If j0 is an automorphism of F associated with ðo; oÞ % and different from j; then for every vertex v of G; either jðZðaÞÞ ¼ j0 ðZðaÞÞ for all arcs a directed from v; or jðZðaÞÞ ¼ j0 ðZðaÞÞ ¼ ðj0 ÞðZðaÞÞ for all arcs a directed from v:

ARTICLE IN PRESS 264

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

Now to prove the lemma it sufﬁces to show that for every automorphism j0 of F associated with ðo; oÞ; % if jðZðaÞÞ ¼ j0 ðZðaÞÞ for all arcs a directed from a vertex of 0 G; then j ¼ j : For every dAF; if jðdÞ ¼ j0 ðdÞ; then jðdÞ ¼ j0 ðdÞ: Let y be the involution of G: For every arc b of G; since ZðybÞAfZðbÞ; ZðbÞg; we have that if jðZðbÞÞ ¼ j0 ðZðbÞÞ; then jðZðybÞÞ ¼ j0 ðZðybÞÞ; hence, by connectivity of G; we get that jðZðaÞÞ ¼ j0 ðZðaÞÞ for all arcs a of G: Since the union of the sets fZðaÞ; ZðaÞg for all arcs a of G is F\f0g; we get that ZðxÞ ¼ Z0 ðxÞ for all xAF; hence Z ¼ Z0 : & Theorem 3. Suppose that the group of automorphisms of a pair /G; ZSARðFÞ has order M: Suppose that there exist N different one-rotations Q for /G; W ðZÞS: Then among these N different cascades ½G; Z; Q there are at least N=2M nonisomorphic cascades. Proof. If ðo; oÞ % is an isomorphism of ½G; Z; Q onto ½G; Z; Q0 ; then ðo; oÞ % is an automorphism of /G; ZS: Given a one-rotation Q for /G; W ðZÞS; there are exactly two different one-rotations Q0 for /G; W ðZÞS such that this ðo; oÞ % is an isomorphism of ½G; Z; Q onto ½G; Z; Q0 (by Lemma 3, there are exactly two different automorphisms j of F associated with ðo; oÞ % and for each of the automorphisms the one-rotation Q0 is deﬁned in the following unique way: for every vertex v of G; if Qv ¼ ða1 ; a2 ; y; am Þ and if ZðoðaÞÞ ¼ jðZðaÞÞ (resp. ¼ jðZðaÞÞ) for all arcs % a directed from v; then Q0oðvÞ ¼ ðoða % 1 Þ; oða % 2 Þ; y; oða % m ÞÞ (resp. ¼ ðoða % m Þ; y; 0 oða % 1 ÞÞÞÞ: Hence. there are at most 2M different cascades ½G; Z; Q (including % 2 Þ; oða ½G; Z; Q) isomorphic to ½G; Z; Q: The relation of isomorphism on the set of all cascades ½G; Z; D; where /G; ZS is a ﬁxed pair, is an equivalence relation, and every equivalence class of the relation contains no more than 2M elements. Hence, among the N different cascades ½G; Z; Q there are at least N=2M nonisomorphic cascades. & Theorem 3 seems to be useful in many applications. In Section 4 this theorem will be applied to obtain families of nonisomorphic nonorientable genus embeddings of complete graphs. Every automorphism of /G; ZSARðFÞ is an automorphism of G: Hence, when we seek the group of automorphisms of /G; ZS; it is natural to proceed in the following way: check for every automorphism ðo; oÞ % of G if this automorphism is an automorphism of /G; ZS; that is, if there exists an automorphism j of F such that for every vertex v of G; either ZðoðaÞÞ ¼ jðZðaÞÞ for all arcs a directed from v; or % ZðoðaÞÞ ¼ jðZðaÞÞ for all arcs a directed from v: % In the case when the group of automorphisms of /G; ZS is complicated or unknown, we can restrict ourselves to the following result that requires only knowledge of the group of automorphisms of G: Theorem 4. Let /G; ZSARðFÞ: Suppose that the group of automorphisms of G has order M 0 : Suppose that there exist N different one-rotations Q for /G; W ðZÞS: Then among these N different cascades ½G; Z; Q there are at least N=2M 0 nonisomorphic cascades.

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

265

Proof. Suppose that the group of automorphisms of /G; W ðZÞS consists of M elements. Since every automorphism of /G; W ðZÞS is an automorphism of G; we N : It remains to apply Theorem 3. & have MpM 0 ; hence N=2M 0 p2M Remark 1. If the group of automorphisms of G consists of the trivial automorphism (the identity mapping) only, then all automorphisms of G are automorphisms of /G; ZS: Hence, in this case Theorems 3 and 4 give the same result: among these N different cascades ½G; Z; Q there are at least N=2 nonisomorphic cascades. By an edge of a digraph G we mean a pair of reverse arcs, these arcs are called the arcs of the edge. By vertices and edges of a cascade ½G; Z; D we mean the vertices and edges of G: An edge of a cascade is of type 0 or 1 if the arcs of the edge are of type 0 or 1, respectively. The degree of a vertex of a cascade is the number of arcs directed from the vertex. A cascade ½G; Z; D can be represented as a ﬁgure of G where the rotations of the vertices are indicated. The black vertices denote a clockwise rotation and the white vertices a counterclockwise rotation. Each pair of reverse arcs with different (inverse) currents is represented by one of the arcs. Each pair of reverse arcs with the same current is depicted as a broken arc. It is customary to depict an end arc as a straight line without an arrow, with a vertex at one end and without a vertex at the other end. In Section 4, when applying Theorem 3, we will use Claims 4 and 5 to construct many different one-rotations for /G; W ðZÞS: Here we need Lemmas 1 and 2. In the lemmas, when speaking about two different ways of choosing rotations of vertices v and w; we mean that we choose two different collections fPv ; Pw g; where Pv and Pw are rotations of v and w; respectively. Let G be a digraph with the involution y: Let u be the initial vertex of an arc a of G: Given a rotation D of G; the ordered pair //a; DaSS is called a corner of the vertex u (for convenience, we enclose the pair in double angular braces). Given /G; W ; DS; we will say that the circuit ðy; ya; Da; yÞ (resp. ðy; Da; yayÞ) for W ; D passes the corner //a; DaSS of the vertex u with normal (resp. alternative) behavior. Let v and w be vertices of G: Let //a; DaSS and //b; DbSS be corners of v and w; respectively. If the corners are passed by two different circuits (resp. by the same circuit such that one corner is passed with normal and the other is passed with alternative behavior), then the pair f//a; DaSS; //b; DbSSg is a consistent pair of corners of the vertices v and w for the circuits (resp. for the circuit). Lemma 4. Let /G; ZSARðFÞ: Suppose that there is a one-rotation D for /G; W ðZÞS: Let a type 0 edge e be incident with two trivalent vertices v and w of G: Then, given D; there are at least two different ways of choosing rotations of v and w; not changing the rotations of other vertices, so that the two resulting different rotations of G are onerotations for /G; W ðZÞS: Proof. Remove the edge e from G: We obtain a digraph G0 with current assignment Z0 such that W ðZ0 Þ ¼ W ðZÞ: Let D0 be the rotation of G0 that coincides with D on the vertices V ðGÞ\fv; wg:

ARTICLE IN PRESS 266

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

Fig. 1.

If a circuit for W ðZÞ; D traversed e in the opposite directions, then the triple /G0 ; W ðZ0 Þ; D0 S has exactly two different circuits (if we consider a circuit to be deﬁned up to reversal), say X and Y ; such that X passes the twovalent vertex v of G0 ; and Y passes the twovalent vertex w of G0 (see Fig. 1(a)). The reader can easily check that there are at least two different consistent pairs of corners of the vertices v and w in G 0 for the circuits X and Y ; and for each such consistent pair we can add the edge e and deﬁne rotations of the trivalent vertices v and w as shown in Fig. 1(b) to get a one-rotation for /G; W ðZÞS: It is easy to see that the collections of rotations of the trivalent vertices v and w deﬁned for the two different consistent pairs of corners are different. If a circuit for W ðZÞ; D traversed e twice in the same direction, then the triple /; G0 ; W ðZ0 Þ; D0 S has exactly one (up to reversal) circuit and the circuit for W ðZ0 Þ; D0 passes one of the twovalent vertices v and w with normal behavior and the other vertex with alternative behavior (Fig. 1(c)). The reader can easily check that there are at least two different consistent pairs of corners of the vertices v and w in G0 for the circuit, and for each such consistent pair we can add the edge e and deﬁne rotations of the trivalent vertices v and w as shown in Fig. 1(d) to get a one-rotation for /G; W ðZÞS: It is easy to see that the collections of rotations of the trivalent vertices v and w deﬁned for the two different consistent pairs of corners are different. & When considering cascades with current group of even order, we need the following lemma. Lemma 5. Let /G; ZSARðFÞ: Suppose that there is a one-rotation D for /G; W ðZÞS: Let a type 0 edge e be incident to two trivalent vertices v and w: Suppose that the pair W ðZÞ; D determines a circuit C that passes the vertices v and w with normal behavior only (see Fig. 2(a) where some pieces of the d-cycle of C are depicted). Then, given D;

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

267

there are at least two different ways of choosing rotations of v and w; not changing the rotations of other vertices, so that the two resulting different rotations Q of G are onerotations for /G; W ðZÞS and for each Q; the pair W ðZÞ; Q determines a circuit such that the d-cycles of the circuit and C have the same dashed pieces. Proof. The proof is more or less obvious but tedious to write out in full, so we merely sketch it. Remove the edge e from G (Fig. 2(b)). We obtain a digraph with the rotation, where the remaining pieces of the d-cycle of C form the d-cycles of two circuits X and Y : Here we have two possible cases shown in Fig. 1(c) (now ignore the wavy lines). It is seen that in both cases we can insert the type 0 edge e (depicted in wavy line) in two different ways to obtain a one-rotation Q for /G; W ðZÞS such that the pair W ðZÞ; Q determines a circuit CðQÞ the d-cycle of which has the same dashed pieces as the d-cycle of C has. One of the circuits CðQÞ is the circuit C; and the dcycle of the other circuit CðQÞ consists of the pieces of the d-cycle of C; but these pieces are glued in a different order. & Two pairs of adjacent vertices of a digraph are called disjoint if the pairs have no common vertices. Claim 4. Let ½G; Z; D be a cascade. Suppose that G has m disjoint pairs of adjacent trivalent vertices. Then there are at least 2m different one-rotations for /G; W ðZÞS: Claim 5. Let ½G; Z; D be a cascade. Suppose that G has m disjoint pairs of adjacent trivalent vertices and that the pair W ðZÞ; D determines a circuit C that passes all the 2m vertices with normal behavior only. Then there are at least 2m different onerotations Q for /G; W ðZÞS such that every pair W ðZÞ; Q determines a circuit such that the d-cycles of the circuit and C have the same dashed pieces. The 2m different one-rotations in Claims 4 and 5 are obtained by applying Lemmas 4 and 5, respectively, to the m disjoint pairs of adjacent trivalent vertices.

Fig. 2.

ARTICLE IN PRESS 268

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

In Section 4, when we give a ﬁgure of a cascade with m disjoint pairs of adjacent trivalent vertices, the pairs are indicated in the following way: for every pair, the arc joining the vertices of the pair has transverse stroke. If ða1 ; a2 ; y; am Þ is the rotation of a vertex of a cascade ½G; Z; D; where Zðai Þ ¼ di for i ¼ 1; 2; y; m; then the cyclic sequence ðd1 ; d2 ; y; dm Þ is called the current rotation of the vertex. If d1 þ d2 þ ? þ dm ¼ 0; the vertex is said to satisfy Kirchhoff’s Current Law (KCL). In what follows we will sometimes consider an element of Zn to be an integer (that is, an element of ZÞ and vice versa, the exact meaning will be always clear from the context. Denote by ðk; tÞ the greatest common divisor of the integers k and t: The onevalent vertices of a cascade are called vortices. Given a vortex, the current g on the arc directed from the vortex is called the current flowing out of the vortex. If Zn is the current group, then the order of g is n=ðn; gÞ: In what follows we will consider cascades with the current group Zn only, satisfying the following construction principles (C1)–(C4): (C1) (C2) (C3) (C4)

Each vertex is trivalent or onevalent. If n is even, then there is exactly one end arc, the arc carries the current n2: Each trivalent vertex satisﬁes KCL. The current ﬂowing out of a vortex has order 3, n2 (when n is even), or n:

Every such cascade generates an embedding of Kn with the vertex set Zn : The face set of the derived embedding is determined as follows. There is a mapping from the face set onto the vertex set of the cascade. Given a vertex of the cascade, the faces mapping onto the vertex are called the faces induced by the vertex, and they are determined by Theorem 4.4.1 which extends to the nonorientable case as well. The following claim is the version of Theorem 4.4.1 [6] which we shall use in the sequel. Claim 6. Let a cascade with the current group Zn satisfy (C1)–(C4). Then a trivalent vertex with the current rotation ðb; g; dÞ induces n triangular faces ½x; x þ b; x þ b þ g; xAZn : Let g be the current flowing out of a vortex. If g has order 3, then the vortex induces triangular faces. If g has order n; then the vortex induces one n-gonal face ½0; g; 2g; y; ðn 1Þg incident to all vertices of the derived graph Kn : If n and g are even, and g has order n2; then the vortex induces two ðn=2Þ-gonal faces: the face ½0; g; 2g; y; ððn=2Þ 1Þg incident to the vertices 0; 2; y; n 2; the face ½1; 1 þ g; 1 þ 2g; y; 1 þ ððn=2Þ 1Þg incident to the vertices 1; 3; y; n 1:

Fig. 3.

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

269

In Section 4 the ﬁgures of cascades will contain the fragment shown in Fig. 3(a). The fragment has two vertical arcs connected by dots, the arcs carry the currents 3k and 3t; respectively, where 3kp3t; and the arcs are directed in the same direction iff t k 0 mod 2: The fragment in Fig. 3(a) is a designation of the ladder-like fragment with exactly t k þ 1 vertical rungs shown in Fig. 3(b). If we consider these t k þ 1 rungs from left to right, then the rungs are directed in alternating fashion up and down, and carry the currents 3k; 3ðk þ 1Þ; 3ðk þ 2Þ; y; 3t; respectively. The horizontal arcs of the ladder-like fragment are directed from left to right and are assigned currents so that KCL holds at every vertex. All vertices on the same horizontal line of the ladder-like fragment have the same rotation (clockwise or counterclockwise). Note that all rungs of the fragment have transverse stroke. The edge joining vertices v and w of a graph is denoted by ðv; wÞ: Two faces of an embedding are adjacent if they share a common edge. A link for vertices v and w of an embedding is every pair ½v; x; y; ½w; y; x of adjacent triangular faces of the embedding. In an embedding of a graph different pairs of vertices may have different numbers of links. The following obvious claim will be of use in Section 4 when, considering two embedding f1 and f2 of a graph, we want to ﬁnd an isomorphism of f1 onto f2 : Claim 7. Let f1 and f2 be embeddings of a graph. If c is an isomorphism of f1 onto f2 ; then vertices v and w of f1 and the vertices cðvÞ and cðwÞ of f2 have the same number of links. Consider a cascade with the current group Zn : For every type 0 edge joining two trivalent vertices, deﬁne the index of the edge as follows: if the current rotations of the vertices are ðb; g; dÞ and ðd; e; mÞ; where d and d are the currents on the arcs of the edge (see Fig. 4(a)), then the index of the edge is g þ e: Since KCL holds at the vertices, the index is well-deﬁned. By Claim 6, the faces induced by the vertices form exactly n links such that the faces of every link share a common edge ðy; y þ dÞ; yAZn (see Fig. 4(b)). These n links are said to be induced by the edge. Now we see that the index is deﬁned so that the following claim holds. Claim 8. Given a cascade with the current group Zn ; an edge with index D induces exactly n links: one link for every pair x; x þ D of vertices, xAZn :

Fig. 4.

ARTICLE IN PRESS 270

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

Fig. 5.

Remark 2. We see that edges with indices D and D induce links for the same pairs of vertices. In Section 4, being interested only in the total number of links between pairs of vertices, we will take the index to be deﬁned up to inversion. That is, in a ﬁgure of a cascade where some edges are additionally labeled by their indices, the edges with indices D and D will be labeled by the same index, say D; and we will say that all the edges have the index D: By inserting a new vertex in a face of an embedding we mean the following: place a new vertex inside the face and join the vertex by disjoint edges with all vertices on the boundary of the face. In Section 4, in some cases, to construct an NG-embedding of a complete graph, we insert new vertices in the nontriangular faces of the derived embedding. Let a cascade have a vortex shown in Fig. 5(a) such that the vortex induces (one or two) nontriangular faces. By Claim 6, every vertex of the derived embedding is incident with exactly one of the faces and appears exactly once in the boundary of the face. Insert a new vertex v in one of the faces (see Fig. 5(b)). If x1 ; x2 ; y; xm are all vertices on the boundary of the face, then the vertex v has exactly one link with pairwise distinct vertices x1 þ d; x2 þ d; y; xm þ d: Hence, every new vertex has no more than one link with every vertex of the derived graph. This property of new vertices will give us a possibility to distinguish the new vertices among the vertices of an NG-embedding, and will help us to ﬁnd an isomorphism between two NG-embeddings of a complete graph. Let v be a vertex of a triangular embedding f of a graph. By the ðvÞ-disc in f we mean the disc formed by the faces incident with v: In Section 4 we will use the following property of the isomorphism between two embeddings. Let f and f 0 be two isomorphic triangular embeddings of a graph. Let c be an isomorphism of f onto f 0 ; and v be an m-valent vertex of f : Clearly, if x; y; z are three consecutive vertices on the boundary of the ðvÞ-disc in f ; then cðxÞ; cðyÞ; cðzÞ are three consecutive vertices on the boundary of the ðcðvÞÞ-disk in f 0 : Hence, c preserves the circular order of the vertices on the boundary of the ðvÞ-disk in f ; that is, if ½w1 ; w2 ; y; wm is the boundary of the ðvÞ-disk in f ; and ½u1 ; u2 ; y; um is the boundary of the ðcðvÞÞ-disk in f 0 ; then ½cðw1 Þ; cðw2 Þ; y; cðwm Þ is either ½u1 ; u2 ; y; um or ½um ; y; u2 ; u1 :

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

271

4. Nonisomorphic nonorientable genus embeddings of complete graphs In this section Theorems 5–8 show that for every integer 0pip11; there are integers mðiÞp9 and hðiÞp9 such that the complete graph K12sþi for sXmðiÞ has at least 22shðiÞ nonisomorphic nonorientable genus embeddings. The integers mðiÞ and hðiÞ are given in the following table: i 0 1 2 3 4 5 6 7 8 9 10 11 mðiÞ 2 2 6 3 2 2 2 2 2 9 3 2 hðiÞ 2 1 6 5 2 4 3 1 4 9 3 3

Theorems 5–8 are proved in a similar way. To avoid repetitions in future, we give below a general scheme according to which each of the theorems is proved. This scheme includes four steps (S1)–(S4) such that for different i these steps are performed in different ways, and gives some reasonings that work for every i: Having this scheme, for every i; the proof of the theorem will contain only steps (S1)–(S4). The reader is referred to the scheme to ﬁll in the missing steps. The cascades used in the proof are taken from [7], in some cases we changed the rotation. To avoid cluttering the ﬁgure of a cascade, we do not display all the currents on the depicted arcs, the ﬁgure contains all information to restore the missing currents using KCL. The scheme is as follows. Given iAf0; 1; y; 11g; let the theorem state that the graph K12sþi ; sXmðiÞ; has at least 2m nonisomorphic NG-embeddings. Proof. (S1) We give a ﬁgure of a cascade ½G; Z; D with the current group Z12sþj ; jpi: The reader will be invited to verify that the construction in the ﬁgure is a cascade satisfying (C1)–(C4). For iAf1; 4; 7g; we have j ¼ i; and the cascade generates an NG-embedding of K12sþi : For ief1; 4; 7g; we have joi; and the cascade generates an embedding of K12sþj such that this embedding can be modiﬁed (adding new vertices, crosscaps, etc.) into an NG-embedding of K12sþi : The digraph G has exactly m þ 1 arcs with transverse stroke. For odd j; Claim 4 gives 2mþ1 different one-rotations Q for /G; W ðZÞS: For even j; the pair W ðZÞ; D determines a circuit C that passes all the vertices incident to the m þ 1 arcs with normal behavior only. In the ﬁgure of ½G; Z; D some pieces of the d-cycle of C will be indicated. The pieces do not pass any vertex incident to an arc with transverse stroke, and the reader can easily check that the pieces include all the dashed pieces of the d-cycle. Now, Claim 5 gives 2mþ1 different one-rotations Q for /G; W ðZÞS such that every pair W ðZÞ; Q determines a circuit the d-cycle of which has the same dashed pieces as the d-cycle of C has.

ARTICLE IN PRESS 272

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

(S2) We show that /G; ZS has no nontrivial automorphisms. For ia8; taking into account that every automorphism of /G; ZS is an automorphism of G; the step (S2) amounts to proving that G has no nontrivial automorphisms. Since /G; ZS has no nontrivial automorphisms, by Theorem 3 and Remark 1, among these 2mþ1 different cascades ½G; Z; Q there are at least ð1=2Þ2mþ1 ¼ 2m nonisomorphic cascades. By Theorem 2, these 2m nonisomorphic cascades determine 2m nonequivalent schemes. For odd j; by Theorem 1, these 2m nonequivalent schemes generate nonisomorphic embeddings of K12sþj : For even j; the cascade ½G; Z; D is constructed in such a way that the following property (P1) holds. (P1) For all Q; the cascades ½G; Z; Q determine the schemes ½P; L with the same set L such that 2jLjoð1=2Þð12s þ jÞ: Hence, by Theorem 1, these 2m nonequivalent schemes generate nonisomorphic embeddings of K12sþj : The validity of (P1) is veriﬁed in the following way. As has been stated above, every pair W ðZÞ; Q determines a circuit the d-cycle of which has the same dashed pieces as the d-cycle of the circuit C for W ðZÞ; D has, that is, all the cascades ½G; Z; Q have the same arcs traversed by a circuit for W ðZÞ; Q twice in the same direction. Taking into account that the arcs of the cascade ½G; Z; D traversed by the circuit C exactly once with alternative behavior are all arcs traversed by the circuit twice in the same direction, one can count the number l of arcs traversed by the circuit C twice in the same direction, and then check that 4l ¼ 2jLjoð1=2Þð12s þ jÞ: Obviously, (P1) holds in the case i ¼ 8 where the cascade has no broken arcs. Now we have the 2m nonisomorphic cascades ½G; Z; Q generating nonisomorphic embeddings f ðQÞ of K12sþj : Different embeddings of the same graph have the same vertex set. If two embeddings of a graph have a face ½v1 ; v2 ; y; vm ; then this face is called a common face of the embeddings. All the embeddings f ðQÞ have the same vertex set and have some common faces, the faces are induced by the vertices of the cascade ½G; Z; D that are not incident to arcs with transverse stroke. For iAf1; 4; 7g; the embedding f ðQÞ is a triangular NG-embedding of K12sþ4 : For ief1; 4; 7g; a cascade ½G; Z; Q has vortices (one or two) that induce ð12s þ jÞgonal or ðð1=2Þð12s þ jÞÞ-gonal faces. Inserting new vertices in the nontriangular faces % of f ðQÞ we obtain the embedding fðQÞ: For iAf0; 3; 6; 10g; the cascade ½G; Z; Q has exactly one vortex (the vortex induces one ð12s þ jÞ-gonal face incident to all vertices % of K12sþj Þ; and the embedding fðQÞ is a triangular NG-embedding of K12sþi : For ˆ % iAf2; 5; 8; 9; 11g; the embedding fðQÞ is modiﬁed into an NG-embedding fðQÞ of ˆ % K12sþi : All the embeddings fðQÞ have the same vertex set, and all the embeddings fðQÞ have the same vertex set too. The modiﬁcations have the property that during the ˆ % % modiﬁcation of f ðQÞ into fðQÞ (resp. fðQÞ into fðQÞÞ only faces common to all f ðQÞ ˆ % % (resp. fðQÞÞ vanish, and the new faces that appear are common to all fðQÞ (resp. fðQÞÞ: % (S3) (For iAf2; 5; 8; 9; 11g only) We describe the modiﬁcation of fðQÞ into an NGˆ embedding fðQÞ of K12sþi :

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

273

To prove that the constructed embedding of K12sþi in a surface is an NGembedding, we have to show that the surface is nonorientable and that, for nontriangular embeddings, the genus of the surface is Jð1=6Þð12s þ i 3Þð12s þ i 4Þn (see [10, Chapter 4.5]). We leave it to the reader to calculate the genus of the surface. The nonorientability of the embedding is shown in the following way. For i ¼ 1; 6; 9; 10 (when the embedding is triangular), the genus of the surface is odd, ˆ hence the surface is nonorientable. For i ¼ 2; 5; 8; 11; the embedding fðQÞ is obtained % from fðQÞ by attaching crosscaps, hence the surface is nonorientable. For i ¼ 0; 3; 4; 7; it sufﬁces to show that f ðQÞ is nonorientable, that is, that the derived graph has a cycle with an odd number of type 1 arcs (see [6, p. 110]). The reader can easily verify that, for i ¼ 0; 3; 4; in every cascade ½G; Z; Q a circuit traverses an arc with some current d twice in the same direction, and the arc with current 1 twice in opposite directions, hence, all arcs ½z; z þ d of the derived graph are of type 1, and all arcs ½z; z 1 are of type 0. It follows that the cycle ½0; d; ½d; d 1; ½d 1; d 2; y; ½2; 1; ½1; 0 has exactly one type 1 arc, namely ½0; d; hence the embedding f ðQÞ is nonorientable. For i ¼ 7 and every cascade ½G; Z; Q; considering the triple /G; W ðZÞ; QS; one can see that G has a cycle with an odd number of type 1 arcs, hence, the triple generates a b; that is, there is an arc of G traversed by the circuit nonorientable embedding of G twice in the same direction. Hence, the cascade ½G; Z; Q determines a scheme ½P; L where W a|; and the scheme determines the triple /K% 12sþ7 ; W ; DS; where W a|: Now it remains to show that in K% 12sþ7 there is a cycle with an odd number of type 1 arcs. Suppose (reductio ad absurdum) that K% 12sþ7 has no such cycle.Then there is a S partitioning V1 V2 of the vertex set of K% 12sþ7 such that x; yAW (that is, y xAL) iff xAVi and yAVj ; iaj: A vertex xAVi for every iAf1; 2g is the initial vertex of exactly jLj type 1 arcs, hence jVj j ¼ jLj is even for jai; a contradiction, since jV1 j þ jV2 j ¼ 12s þ 7: Now, to complete the proof of the theorem, it sufﬁces to prove the following claim. Claim 9. If f ðQ1 Þ and f ðQ2 Þ are nonisomorphic, then: % 1 Þ and fðQ % 2 Þ are nonisomorphic also; (a) for ia4; fðQ ˆ 2 Þ are nonisomorphic also. ˆ 1 Þ and fðQ (b) for iAf2; 5; 8; 9; 11g; fðQ Now we prove (a) from Claim 9. It sufﬁces to show that if c is an isomorphism of % 2 Þ; then the restriction of c to the vertices of f ðQ1 Þ is an isomorphism % 1 Þ onto fðQ fðQ of f ðQ1 Þ onto f ðQ2 Þ: The vertices of f ðQÞ are called basic vertices. A face incident to basic vertices only is called a basic face. A basic link consists of two adjacent triangular basic faces. The cascade ½G; Z; D has tX2 edges with the same index; in the ﬁgure of the cascade the index of an arc is indicated in a box connected by line with the arc representing the edge. These t edges are not adjacent to edges with % transverse stroke, hence, for every Q; in f ðQÞ as well as in fðQÞ every basic vertex has at least tX2 basic links with some other basic vertex. When we insert new vertices in

ARTICLE IN PRESS 274

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

% the nontriangular faces of f ðQÞ; each new vertex has in fðQÞ at most one link with every basic vertex, and since nontriangular faces do not share common edges (the vortices are not adjacent vertices), the new vertices do not have links between % themselves. Hence, in fðQÞ every new vertex has at most one link with every other % 1 Þ onto fðQ % 2 Þ; then, by Claim 7, we obtain that vertex. If c is an isomorphism of fðQ % 1 Þ to the new (inserted) vertices of fðQ % 2 Þ: c takes the new (inserted) vertices of fðQ % 1 Þ the isomorphism c preserves the circular order Since for every new vertex v in fðQ of the vertices on the boundary of the ðvÞ-disc, we get that the restriction of c to the vertices of f ðQ1 Þ is an isomorphism of f ðQ1 Þ onto f ðQ2 Þ: The item (a) from Claim 9 having been proved, to prove (b) it sufﬁces to carry out the following step: ˆ 1Þ (S4) (For iAf2; 5; 8; 9; 11g only) We show that if c0 is an isomorphism of fðQ ˆ 2 Þ; then there is an isomorphism c of fðQ % 1 Þ onto fðQ % 2 Þ: onto fðQ Step (S4) completes the proof of the theorem. & In the series of results that follow when carrying out steps (S1)–(S4) we will always keep to the notations introduced in the general description of our scheme. In what follows, to avoid repetitions, several values of i can be considered simultaneously in one theorem. Theorem 5. The graph K12s ; sX2; has at least 22s2 nonisomorphic NG-embeddings. The graph K12sþ1 ; sX2; has at least 22s1 nonisomorphic NG-embeddings. The graph K12sþ3 ; sX3; has at least 22s5 nonisomorphic NG-embeddings. The graph K12sþ4 ; sX2; has at least 22s2 nonisomorphic NG-embeddings. The graph K12sþ6 ; sX2; has at least 22s3 nonisomorphic NG-embeddings. The graph K12sþ7 ; sX2; has at least 22s1 nonisomorphic NG-embeddings. The graph K12sþ10 ; sX3; has at least 22s2 nonisomorphic NG-embeddings. Proof. (S1) The cascade ½G; Z; D for the case i ¼ 0; 3; 4; and 6 is given in Figs. 6(a)– (d), respectively. The cascade ½G; Z; D for the case i ¼ 1; 7 is given in Figs. 7(a) and (b), respectively. The cascade ½G; Z; D for the case i ¼ 10 is given in Fig. 8 depending on the residue class of s modulo 3. (S2) For i ¼ 0; 1; 3; 4; 6; 7; the digraph G has exactly one 3-cycle, hence every automorphism of G must take the 3-cycle to itself. The reader can easily verify that every such automorphism of G is the trivial automorphism. For i ¼ 10; the digraph G has exactly two vortices and the currents ﬂowing out of the vortices have different orders 3 and 12s þ 9; respectively, hence every automorphism of /G; ZS must take every vortex to itself. The reader can easily verify that every such automorphism of G is trivial, hence /G; ZS has no nontrivial automorphisms. & Theorem 6. The graph K12sþ2 ; sX6; has at least 22s6 nonisomorphic NG-embeddings. The graph K12sþ5 ; sX2; has at least 22s4 nonisomorphic NG-embeddings.

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

275

Fig. 6.

The graph K12sþ11 ; sX2; has at least 22s3 nonisomorphic NG-embeddings. Proof. (S1) The cascade ½G; Z; D for the case i ¼ 2; 5 and 11 is given in Figs. 9(a),(b), and (c), respectively. (S2) For i ¼ 5; 11; the digraph G has exactly one 3-cycle, hence every automorphism of G must take the 3-cycle to itself. The reader can easily verify that every such automorphism of G is the trivial automorphism. For i ¼ 2; every automorphism of G takes the vortices to the vortices, and the end arc to the end arc.

ARTICLE IN PRESS 276

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

Fig. 7.

The reader can easily verify that every such automorphism of G is the trivial automorphism. The following two steps we consider simultaneously for all three cases of i: (S3) Let ½G; Z; D be one of the cascades with the current group Zn : A cascade ½G; Z; Q generates an embedding f ðQÞ of Kn such that two faces of the embedding are n-gonal and each of them is incident to all vertices of Kn ; and all the remaining faces are triangular. Insert new vertices x and y in the two n-gonal faces. We obtain a % triangular embedding fðQÞ of Knþ2 K2 with two nonadjacent vertices x and y: Using one additional crosscap, it is easy to provide for the missing adjacency as shown in Figs. 10(a) and (b), where v is an arbitrary basic vertex chosen to be the same for all Q (in Fig. 10, as in what follows, the crosscap is depicted as a blank ˆ circle with the letter M inside). This way we construct an NG-embedding fðQÞ of Knþ2 : ˆ 1 Þ onto fðQ ˆ 2 Þ; then c0 is an (S4) Now we show that if c0 is an isomorphism of fðQ % % % isomorphism of fðQ1 Þ onto fðQ2 Þ: In the course of the modiﬁcation of fðQÞ; two triangular faces (marked by stars) in Fig. 10(a) vanish and two quadrangular faces % (marked by stars) appear in Fig. 10(b), the remaining faces of fðQÞ are not changed. ˆ The two quadrangular faces are shown in Fig. 10(c). In fðQÞ every basic vertex has two links with some other basic vertex, each of the vertices x and y has at most one

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

277

Fig. 8.

ˆ link with every vertex of fðQÞ; hence fc0 ðxÞ; c0 ðyÞg ¼ fx; yg: Since there are exactly ˆ (namely x; y; and vÞ; three vertices of Knþ2 incident with both 4-gonal faces of fðQÞ 0 we get c ðvÞ ¼ v: Since u and w are unique vertices incident with exactly one 4-gonal face, we get fc0 ðuÞ; c0 ðwÞg ¼ fu; wg: Now considering Fig. 10(c), we see that there are two cases: Case 1: c0 ðxÞ ¼ x; c0 ðyÞ ¼ y; c0 ðvÞ ¼ v; c0 ðwÞ ¼ w; c0 ðuÞ ¼ u: Case 2: c0 ðxÞ ¼ y; c0 ðyÞ ¼ x; c0 ðvÞ ¼ v; c0 ðwÞ ¼ u; c0 ðuÞ ¼ w: ˆ 1 Þ we have that ½c0 ðz1 Þ; c0 ðz2 Þ; c0 ðz3 Þ is a For every triangular face ½z1 ; z2 ; z3 of fðQ ˆ 2 Þ: The embedding fðQÞ % is a triangular embedding. The set of triangular face of fðQ ˆ % faces of fðQÞ is the set of the triangular faces of fðQÞ except the faces ½x; v; u and ½v; y; w: One can easily check that for both Cases 1 and 2 we have

ARTICLE IN PRESS 278

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

Fig. 9.

f½c0 ðxÞ; c0 ðvÞ; c0 ðuÞ; ½c0 ðvÞ; c0 ðyÞ; c0 ðwÞg ¼ f½x; v; u; ½v; y; wg; that is, c0 is an % 1 Þ onto fðQ % 2 Þ: & isomorphism of fðQ Theorem 7. The graph K12sþ8 ; sX2; has at least 22s4 nonisomorphic NG-embeddings. Proof. (S1) The cascade ½G; Z; D is given in Fig. 11.

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

279

Fig. 10.

Fig. 11.

(S2) The digraph G has exactly two onevalent vertices (vortices), and the unique nontrivial automorphism of G takes every vortex to the other vortex. The currents ﬂowing out of the vortices have different orders 6s þ 3 and 12s þ 6; respectively, hence /G; ZS has no nontrivial automorphisms. (S3) A cascade ½G; Z; Q has exactly two vortices and the currents ﬂowing out of the vortices are 1 (of order 12s þ 6) and ð6s þ 2Þ (of order 6s þ 3), respectively. The cascade generates an orientable embedding f ðQÞ of K12sþ6 such that: one face is ð12s þ 6Þ-gonal and incident to all vertices of K12sþ6 (we insert a new vertex x in this face); two faces are ð6s þ 3Þ-gonal, one of them is incident to all even vertices 0; 2; y; 12s þ 4 of K12sþ6 (insert a new vertex y0 in the face), and the other face is incident to all odd vertices 1; 3; y; 12s þ 5 of K12sþ6 (insert a new vertex y1 in the % face); all the remaining faces are triangular. We obtain the embedding fðQÞ: Fig. 12 shows how, by adding two crosscaps, one can identify the vertices y0 and y1 into a new vertex y; and then gain the adjacency ðx; yÞ: As a result of the ˆ modiﬁcation in Fig. 12 we obtain an NG-embedding fðQÞ of K12sþ8 with the vertex set f0; 1; y; 12s þ 5; x; yg: ˆ 1 Þ onto fðQ ˆ 2 Þ; then there is an (S4) We show that if c0 is an isomorphism of fðQ % % isomorphism c of fðQ1 Þ onto fðQ2 Þ: The cascade ½G; Z; Q has three edges with the % same index, hence, in fðQÞ every basic vertex has at least three basic links with some ˆ % other basic vertex. In the course of the modiﬁcation of fðQÞ into fðQÞ; three

ARTICLE IN PRESS 280

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

Fig. 12.

triangular faces (marked by stars) in Fig. 12(a) vanish and two new triangular and one new 5-gonal face (marked by stars) appear in Fig. 12(b). The modiﬁcation does not change the basic links, hence: ˆ (P2) In fðQÞ every basic vertex has at least three (basic) links with some other basic vertex. % In fðQÞ the vertex x has exactly one link with every basic vertex and has no links with y0 and y1 : During the modiﬁcation in Fig. 12, the vertex x looses the link with

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

281

% the vertex d and gain an extra link with each of the vertices 6s þ 3 and 6s þ 4: In fðQÞ the vertex y0 (resp. y1 Þ has exactly 6s þ 3 links: one link with every odd (resp. even) ˆ basic vertex. In fðQÞ the vertex y has 12s þ 6 links: one link with every basic vertex except the vertices b and g; plus one new link with each of the vertices 1 and 2. ˆ Hence, in fðQÞ each of the vertices x and y has no more than two links with every other vertex. By Claim 7, taking (P2) into account, we obtain fc0 ðxÞ; c0 ðyÞg ¼ fx; yg: From the vertices x and y; only the vertex y is incident with the 5-gonal face, hence (P3) c0 ðxÞ ¼ x; c0 ðyÞ ¼ y: ˆ For every Q; the faces of fðQÞ incident with the vertex y form the same disc shown in Fig. 13. Since the isomorphism c0 preserves the circular order of the vertices on the boundary of the disc, taking (P3) into account, we obtain that there are two cases: Case 1: c0 ðvi Þ ¼ vi and c0 ðwi Þ ¼ wi for all i ¼ 0; 1; y; 6s þ 2: Case 2: c0 ðvi Þ ¼ wi and c0 ðwi Þ ¼ vi for all i ¼ 0; 1; y; 6s þ 2: % 1 Þ onto fðQ % 2 Þ can be deﬁned as Now we show that an isomorphism c of fðQ follows: % 1 Þ: In Case 1: cðy0 Þ ¼ y0 ; cðy1 Þ ¼ y1 ; cðuÞ ¼ c0 ðuÞ for every other vertex u of fðQ 0 % 1 Þ: In Case 2: cðy0 Þ ¼ y1 ; cðy1 Þ ¼ y0 ; cðuÞ ¼ c ðuÞ for every other vertex u of fðQ By deﬁnition of c; one can check that ½cðxÞ; cðv0 Þ; cðw0 Þ ¼ ½x; v0 ; w0 is a face of % 1 Þ different from ½x; v0 ; w0 such that % 2 Þ; and that for every face ½z1 ; z2 ; z3 of fðQ fðQ z1 ; z2 are basic vertices and z3 is either x or a basic vertex, we have that % 2 Þ: The faces of fðQ % 1 Þ incident with y0 and y1 are ½cðz1 Þ; cðz2 Þ; cðz3 Þ is a face of fðQ ½vi ; viþ1 ; y0 and ½wi ; wiþ1 ; y1 ; respectively, where i ¼ 0; 1; y; 6s þ 2 (addition is % 1 Þ; jAf0; 1g; modulo 6s þ 3Þ: By deﬁnition of c; we get that if ½z; z0 ; yj is a face of fðQ 0 % % 1 Þ onto then ½cðzÞ; cðz Þ; cðyj Þ is a face of fðQ2 Þ: Hence, c is an isomorphism of fðQ % fðQ2 Þ: &

Fig. 13.

ARTICLE IN PRESS 282

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

Theorem 8. The graph K12sþ9 ; sX9; has at least 22s9 nonisomorphic NG-embeddings. Proof. (S1) The cascade ½G; Z; D is given in Fig. 14. (S2) The digraph G has exactly one vortex and exactly one 2-cycle, hence every automorphism of G must take the vortex to itself, and the 2-cycle to itself. The reader can easily verify that every such automorphism of G is the trivial automorphism. (S3) A cascade ½G; Z; Q has exactly one vortex. The cascade generates an embedding f ðQÞ of K12sþ8 such that: one face is ð6s þ 4Þ-gonal and incident to all even vertices 0; 2; y; 12s þ 6 (insert a new vertex x0 in the face); one face is ð6s þ 4Þgonal and incident to all odd vertices 1; 3; y; 12s þ 7 (insert a new vertex x1 in the % % face); all the remaining faces are triangular. We obtain the embedding fðQÞ: In fðQÞ the vertex x0 (resp. x1 Þ has exactly one link with every odd (resp. even) vertex. The cascade has the fragment shown in Fig. 15. It is seen that the log of the circuit is 6s 3; 2; 2; 6s 1; 4; y; ð6s þ 1Þ; ð6s 3Þ; ð6s 1Þ; ð6s 5Þ; y; % hence, in fðQÞ the faces incident with an arbitrary odd vertex of K12sþ8 are arranged as shown in Fig. 16. % Now we describe sequence (M1)–(M3) of modiﬁcations of fðQÞ that yields a ˆ triangular nonorientable embedding fðQÞ of K12sþ9 : (M1) Identify the new vertices x0 and x1 into a new vertex x as shown in Fig. 17. The two triangular faces (marked by stars) in Fig. 17(a) vanish and three new % triangular faces (marked by stars) appear in Fig. 17(b). The remaining faces of fðQÞ

Fig. 14.

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

283

Fig. 15.

Fig. 16.

are unchanged (if we take xi and x to be the same vertex). The vanished faces are shown in Fig. 18(a) and the new faces are shown in Fig. 18(b). We see that during (M1) the vertex x lost the link with the vertex 10 and got one additional link with 2: (M2) The fragment in Fig. 15 contains two adjacent vertices shown in Fig. 19(a). The vertices induce a pair of adjacent faces depicted in Fig. 19(b) in bold line. The diagonal ﬂip in the pair of adjacent faces replaces the edge ð0; 6s 3Þ depicted as a solid line by the edge ð4; 2Þ depicted as a dashed line. As a result, we have lost the edge ð0; 6s 3Þ and gained an extra edge ð4; 2Þ: During (M2), the vertex x lost the link with 6s 3 and got one additional link with 4: For every vertex wAf4; 8; y; 12s þ 4g of the embedded graph deﬁne a modiﬁcation TðwÞ consisting of the following three diagonal ﬂips: start with the two diagonal ﬂips shown in Fig. 20; then carry out the diagonal ﬂip in the pair of adjacent faces shown in Fig. 21(a), this pair of faces is induced by the two adjacent vertices in Fig. 15 which also appear in Fig. 21(b). Considering Fig. 20, we get (P4) During TðwÞ; the vertex x loses one link with w 10 and w 12; and get one new link with w 2 and w þ 4: As a result of the modiﬁcation TðwÞ; we loose the edge ðw; w þ 2Þ and gain a new edge ðw 12; w 10Þ: It is worth noticing that since distinct vertices w1 ; w2 Af4; 8; y; 12s þ 4g are not neighbors on the ðxÞ-disc formed after having done (M1), we can always carry out Tðw2 Þ after completing Tðw1 Þ:

ARTICLE IN PRESS 284

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

Fig. 17.

Fig. 18.

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

285

Fig. 19.

Fig. 20.

Fig. 21.

(M3) Consider the following sequence of 2s þ 1 modiﬁcations of the form TðwÞ: Tð4Þ; Tð4 12Þ; Tð4 12 2Þ; y; Tð4 12 2sÞ: Since 4 12ð2s þ 1Þ ¼ 2ð12s þ 8Þ 0 mod 12s þ 8; as a result of these 2s þ 1 modiﬁcations, we have lost an extra edge ð4; 2Þ and gained the missing edge (0;2). ˆ We have obtained a triangular nonorientable embedding fðQÞ of K12sþ9 :

ARTICLE IN PRESS 286

V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

Fig. 22.

Taking (P4) into account, the reader can check that during (M3) the vertex x lost a link with vertices 4, 12k for k ¼ 1; 2; y; s; and 12k þ 6 for k ¼ 0; 1; y; s 1; and got a new link with vertices 4; 12k þ 8 for k ¼ 0; 1; y; s 1; and 12k þ 10 for k ¼ 0; 1; y; s 1: Now, after having done (M1)–(M3), the vertex x has exactly three links with the vertex 4; has exactly two links with the vertices 2; 12k þ 8 for k ¼ 0; 1; y; s 1; and 12k þ 10 for k ¼ 0; 1; y; s 2; has no links with the vertices 4; 6s 3; 12k for k ¼ 1; 2; y; s; and 12k þ 6 for k ¼ 0; 1; y; s 1; and has exactly one link with every other basic vertex. Note that the vertex x has exactly one link with every odd vertex, except 6s 3: ˆ 1 Þ onto fðQ ˆ 2 Þ; then c0 is the (S4) First we show that c0 is an isomorphism of fðQ 0 identity mapping (that is, c ðuÞ ¼ u for every vertex u). Denote by B the set of the % vertices of the cascade ½G; Z; Q incident to arcs with index 3 indicated. In fðQÞ every basic vertex has 4 basic link with some other basic vertex, these links are formed by faces induced by vertices from B: During (M1)–(M3) we remove one basic face [0,2,6s 1] and then we perform diagonal ﬂips in some pairs of adjacent basic faces, all these faces are induced by vertices of the fragment in Fig. 15. It is easy to see that if we remove a basic face induced by a vertex v of the cascade, or perform a diagonal ﬂip in the pair of adjacent basic faces induced by vertices v and w; we can destroy only those basic links that consist of faces induced by v; w; and the vertices of the cascade adjacent to v and w: Since the vertices from B are not adjacent to the vertices of the fragment in Fig. 15, we obtain that the modiﬁcations (M1)–(M3) do not ˆ change the 4 basic links between pairs of basic vertices, hence, in fðQÞ every basic ˆ vertex has at least 4 (basic) links with some other basic vertex. Since in fðQÞ the vertex x has at most 3 links with every other vertex, we get c0 ðxÞ ¼ x: Now consider the ðxÞ-disc after having done (M1). This disc is shown in Fig. 22(a) in solid and wavy lines. The modiﬁcation (M2) does not change the disc. The modiﬁcation TðwÞ changes the disc as shown in Fig. 22: the edges depicted as wavy

ARTICLE IN PRESS V.P. Korzhik, H.-J. Voss / Journal of Combinatorial Theory, Series B 91 (2004) 253–287

287

ˆ lines are replaced by new edges depicted as dashed lines. In fðQÞ the vertex 4 is the 0 unique vertex with which the vertex x has 3 links, hence c ð4Þ ¼ 4: After having ˆ done (M3), the boundary of the ðxÞ-disc in fðQÞ has a fragment shown in Fig. 22(b), hence the vertices 2; 6s 5; 4; 6; 6s 9 are consecutive vertices on the boundary of the ðxÞ-disc. Since c0 ð4Þ ¼ 4 and c0 preserves the circular order of the vertices on the boundary of the ðxÞ-disc, we get that there must be either c0 ð2Þ ¼ 2 or ˆ the vertex x has two links with the vertex 2 and c0 ð2Þ ¼ 6s 9; but in fðQÞ exactly one link with the vertex 6s 9; hence c0 ð2Þ ¼ 2: It follows that c0 ðuÞ ¼ u for every vertex u on the boundary of the ðxÞ-disc, hence c0 is the identity mapping. ˆ 2 Þ have the same faces. During the modiﬁcations (M1)– ˆ 1 Þ and fðQ We see that fðQ ˆ % (M3), some faces of fðQÞ (the same faces for all QÞ are replaced by new faces of fðQÞ (the same faces for all QÞ: Hence, if we deﬁne cðx0 Þ ¼ x0 ; cðx1 Þ ¼ x1 ; cðuÞ ¼ u for % 1 Þ; then c is an isomorphism of fðQ % 1 Þ onto fðQ % 2 Þ (and is every other vertex u of fðQ the identity mapping). &

Acknowledgments We are grateful to the referees for many helpful comments and suggestions.

References [1] J.L. Arocha, J. Bracho, V. Neumann-Lara, Tight and untight triangulations of surfaces by complete graphs, J. Combin. Theory Ser. B 63 (1995) 185–199. [2] D.W. Barnette, Generating the triangulations of the projective plane, J. Combin. Theory Ser. B 33 (1982) 222–230. [3] C.P. Bonnington, M.J. Grannell, T.S. Griggs, J. Siran, Exponential families of non-isomorphic triangulations of complete graphs, J. Combin. Theory Ser. B 78 (2000) 169–184. [4] J. Bracho, R. Strauz, Nonisomorphic complete triangulations of a surface, Discrete Math. 232 (2001) 11–18. [5] M.J. Grannell, T.S. Griggs, J. Siran, Recursive constructions for triangulations, J. Graph Theory 39 (2002) 87–107. [6] J.L. Gross, T.W. Tucker, Topological Graph Theory, Wiley, New York, 1987. [7] V. Korzhik, Another proof of the Map Color Theorem for nonorientable surfaces, J. Combin. Theory Ser. B 86 (2002) 221–253. [8] V. Korzhik, H.-J. Voss, On the number of nonisomorphic orientable regular embeddings of complete graphs, J. Combin. Theory Ser. B 81 (2001) 58–76. [9] V. Korzhik, H.-J. Voss, Exponential families of nonisomorphic nontriangular orientable genus embeddings of complete graphs, J. Combin. Theory Ser. B 86 (2002) 186–211. [10] G. Ringel, Map Color Theorem, Springer, Berlin, 1974. [11] G. Ringel, The combinatorial map color theorem, J. Graph Theory 1 (1977) 141–155.