Auxiliary embeddings and constructing triangular embeddings of joins of complete graphs with edgeless graphs

Auxiliary embeddings and constructing triangular embeddings of joins of complete graphs with edgeless graphs

Discrete Mathematics 339 (2016) 712–720 Contents lists available at ScienceDirect Discrete Mathematics journal homepage: www.elsevier.com/locate/dis...

586KB Sizes 0 Downloads 26 Views

Discrete Mathematics 339 (2016) 712–720

Contents lists available at ScienceDirect

Discrete Mathematics journal homepage: www.elsevier.com/locate/disc

Auxiliary embeddings and constructing triangular embeddings of joins of complete graphs with edgeless graphs Vladimir P. Korzhik ∗ National University of Chernivtsi, Chernivtsi, Ukraine Institute of Applied Problems of Mechanics and Mathematics of National Academy of Science of Ukraine, Lviv, Ukraine

article

info

Article history: Received 20 June 2015 Received in revised form 14 September 2015 Accepted 28 September 2015 Available online 11 November 2015 Keywords: Topological embedding Complete graph Join of graphs Triangular embedding

abstract Until recently there were no results on the orientable or nonorientable genus of graphs Kn + Km for n/2 ≤ m < n − 1. Recently, using index one current graphs, McCourt (2014) constructed a nonorientable triangular embedding of K36t +3 +K18t +1+6i for i = 0, 1, . . . , t − 1 and t ≥ 1. In the present paper, using index three current graphs, we construct auxiliary embeddings that allow three arbitrary triangular embeddings of Kn+1 to be incorporated into a triangular embedding of K3n + Km for many cases where m can lie anywhere in the interval 1 ≤ m ≤ 2n. Using these auxiliary embeddings we construct the following six classes of triangular embeddings: orientable triangular embeddings of K36t +6 + K1+2i for t ≥ 1 and i = 0, 1, . . . , 12t, K36t +18 + K1+2i for t ≥ 0 and i = 0, 1, . . . , 12t + 4, and nonorientable triangular embeddings of K18t + K1+2i for t ≥ 1 and i = 0, 1, . . . , 6t − 2, K18t +6 + K1+2i for t ≥ 1 and i = 0, 1, . . . , 6t, K18t −3 + Ki for t ≥ 2 and i = 3, 4, . . . , 12t − 6, K18t +9 + Ki for t ≥ 1 and i = 3, 4, . . . , 12t + 2. Using these auxiliary embeddings we also show that for a certain positive constant a and for an infinite number of values of t, the number of nonisomorphic orientable triangular embeddings of K36t +6 + K1+2i for t ≥ 1 and every i ∈ {0, 1, . . . , 12t } is at least (36t + 6)a(36t +6) −o((36t +6) ) as t → ∞. Analogous results are obtained for the other five classes of triangular embeddings as well. © 2015 Elsevier B.V. All rights reserved. 2

2

1. Introduction The orientable (resp. nonorientable) genus of a connected graph is the minimum genus of an orientable (resp. nonorientable) surface in which the graph can be embedded. A cellular embedding of a graph is triangular if all faces are 3-gonal. An orientable (resp. nonorientable) triangular embedding of a graph without loops and multiple edges is an orientable (resp. nonorientable) minimum genus embedding of the graph. A face of a cellular embedding of a graph is called a hamilton face if the facial walk of the face is a hamilton cycle of the graph. The graph Kn + Km , the join of the complete graph Kn with the edgeless graph Km , can be also thought of as the graph Kn+m − Km , the graph Kn+m where we remove the edges of a subgraph Km . Notice that Kn + Km has an orientable (resp. nonorientable) triangular embedding if and only if Kn has an orientable (resp. nonorientable) embedding such that there are m hamilton faces and all other faces are triangular. Constructing triangular embeddings of graphs Kn + Km , m ≤ 5, was a major step in determining the orientable and nonorientable genus of the complete graphs in the course of proving the Map Color Theorem [15]. Triangular embeddings



Correspondence to: Bogomoltsa St. 3/5, Chernivtsi, 58001, Ukraine. E-mail address: [email protected]

http://dx.doi.org/10.1016/j.disc.2015.09.031 0012-365X/© 2015 Elsevier B.V. All rights reserved.

V.P. Korzhik / Discrete Mathematics 339 (2016) 712–720

713

of some graphs Kn + Km were also constructed while solving some other problems (for example, constructing minimal triangulations of surfaces [11]). As a result, triangular embeddings of many graphs Kn + Km , m ≤ 6, had been constructed. Korzhik [12] using index two and three current graphs constructed orientable and nonorientable triangular embeddings of Kn + Km for many cases where m can lie anywhere in the interval 0 < m < n/2. Craft [1] has shown that Kn + Km has the same orientable genus as Kn,m when n is even and m ≥ 2n − 4. Ellingham and Stephens [2,3] have shown that Kn + Km has the same nonorientable genus as Kn,m for every n ≥ 3 and m ≥ n − 1, and the same orientable genus as Kn,m for even n and m ≥ n (they also determined the orientable genus of some graphs Kn + Km for odd n and m ≥ n). Until recently there were no results on the orientable or nonorientable genus of Kn + Km for n/2 ≤ m < n − 1. Here the main problem has been to find an approach that can be applied to construct minimum genus embeddings of such graphs. Recently, using index one current graphs, McCourt [14] constructed a nonorientable triangular embedding of K36t +3 + K18t +1+6i for t ≥ 1 and i = 0, 1, . . . , t − 1. Recursive constructions based on index three current graphs were used [15,13] to construct triangular embeddings of complete graphs. In the present paper we show that by interchanging currents on arcs of such index three current graphs we obtain current graphs generating auxiliary embeddings that can be used to construct triangular embeddings of graphs Kn + Km , where n/2 ≤ m ≤ 2n/3 and n ≡ 0 (mod 3). In our approach, the constructed auxiliary embeddings allow three arbitrary triangular embeddings of Kn+1 to be incorporated into a triangular embedding of K3n + Km for many cases where m can lie anywhere in the interval 1 ≤ m ≤ 2n. Euler’s formula allows a possibility for the following graphs Kn + Km , m < n − 1, n ≡ 0 (mod 3), to have a triangular embedding: the graphs K12s + K2i for i = 0, 1, . . . , 6s − 1, the graphs K12s+3 + Ki for i = 0, 1, . . . , 12s + 2, and the graphs K12s+6 +K1+2i for i = 0, 1, . . . , 6s+2 can have an orientable triangular embedding; the graphs K6q +Ki for i = 0, 1, . . . , 6q−1, and the graphs K6q+3 + Ki for i = 0, 1, . . . , 6q + 2 can have a nonorientable triangular embedding. In the present paper we construct the following six classes of triangular embeddings: orientable triangular embeddings of K36t +6 + K1+2i for t ≥ 1 and i = 0, 1, . . . , 12t, K36t +18 + K1+2i for t ≥ 0 and i = 0, 1, . . . , 12t + 4, and nonorientable triangular embeddings of K18t + K1+2i for t ≥ 1 and i = 0, 1, . . . , 6t − 2, K18t +6 + K1+2i for t ≥ 1 and i = 0, 1, . . . , 6t, K18t −3 + Ki for t ≥ 2 and i = 3, 4, . . . , 12t − 6, K18t +9 + Ki for t ≥ 1 and i = 3, 4, . . . , 12t + 2. Hence, triangular embeddings of graphs Kn + Km , n/2 ≤ m < 2n/3, are constructed. Note that as a byproduct of using our auxiliary embeddings we obtain in a different way triangular embeddings of those graphs Kn + Km , 0 < m < n/2, for which triangular embeddings have already been constructed in [12]. The constructed auxiliary embeddings give us a possibility to obtain some results on the number of nonisomorphic triangular embeddings of Kn + Km . We show that there is a certain positive constant a such that for an infinite set of values of t, the number of nonisomorphic orientable triangular embeddings of K36t +6 + K1+2i for t ≥ 1 and every i ∈ {0, 1, . . . , 12t } is at least (36t + 6)a(36t +6) −o((36t +6) ) as t → ∞ (notice that this lower bound does not depend on i). Analogous results are obtained for the other five classes of triangular embeddings as well. It is worth noticing that in the case of nonorientable triangular embeddings (four classes of triangular embeddings out of six) these infinite sets of values of t are linear classes. These results suggest the following conjecture. 2

2

Conjecture. There is a certain positive constant a such that for an infinite set of values of n, for every 1 ≤ m ≤ n − 1, the number 2 2 of nonisomorphic minimal orientable or nonorientable embeddings of Kn + Km is at least nan −o(n ) as n → ∞.

It is worth noticing that the lower bound nan −o(n ) in the conjecture does not depend on m. The paper is organized as follows. In Section 2 we prove the main results of the paper. The proofs are based on the existence of auxiliary embeddings constructed in Section 4. These auxiliary embeddings are generated by index three current graphs. To facilitate construction checking in Section 4, some material about index three current graphs is given in Section 3. 2

2

2. Auxiliary embeddings and constructing triangular embeddings Given a face of an embedding, by inserting a new vertex in the face we mean the following: place a new vertex inside the face and join this vertex by disjoint edges with all vertices on the boundary of the face. By an m-hamiltonian embedding (m ≥ 1) of a complete graph we mean an embedding such that exactly m faces are hamilton and all other faces are triangular. Given an m-hamiltonian embedding of Kt , if we insert a new vertex in every hamilton face of the embedding, we obtain a triangular embedding of Kt + Km which is said to be induced by the m-hamiltonian embedding of Kt . If we delete one vertex in a triangular embedding of Kt +1 , we obtain a one-hamiltonian embedding of Kt which is said to be yielded by the triangular embedding of Kt +1 . Consider a (3n)-vertex graph G which is obtained if we take three vertex-disjoint n-cycles C1 , C2 , and C3 (they are called the special cycles of G), and join by an edge every pair of vertices not belonging to the same special cycle. By an embedding

714

V.P. Korzhik / Discrete Mathematics 339 (2016) 712–720

R(3n|m) we mean an embedding of the graph G in a surface such that there are three n-gonal faces with boundaries C1 , C2 , and C3 , respectively, there are m hamilton faces, and all other faces are triangular. We will refer to an embedding R(3n|m) as an auxiliary embedding. Notice that such embeddings R(3n|m) may be possible only for particular cases of (3n, m). Claim 1. If there exists an embedding R(3n|m) and if there exist triangular embeddings of Kn+1 , then there exists a triangular embedding of K3n + Km . Proof. Take three one-hamiltonian embeddings T1 , T2 , and T3 of Kn yielded by triangular embeddings of Kn+1 , where for i = 1, 2, 3, the n-gonal face of Ti is bounded by a hamilton cycle C¯ i of Kn . In the embeddings R(3n|m) and Ti , i = 1, 2, 3, delete the interior of all n-gonal faces. Then for i = 1, 2, 3, identify the special cycle Ci with C¯ i . We obtain an m-hamiltonian embedding of K3n inducing a triangular embedding of K3n + Km .  Remark 1. If in Claim 1 the embedding R(3n|m) is orientable and if we take one-hamiltonian embeddings T1 , T2 , and T3 of Kn yielded by orientable triangular embeddings of Kn+1 , then the obtained triangular embedding of K3n + Km is orientable as well. If we take one-hamiltonian embeddings of Kn yielded by nonorientable triangular embeddings of Kn+1 , then the obtained triangular embedding of K3n + Km is nonorientable whether or not the embedding R(3n|m) is orientable. Theorem 1. There is an orientable triangular embedding of K36t +6 +K1+2i for i = 0, 1, . . . , 12t and t ≥ 1, and of K36t +18 +K1+2i for i = 0, 1, . . . , 12t + 4 and t ≥ 0. Proof. In Section 4 we construct an orientable embedding R(6s|1 + 2i) for s ≥ 3 and i = 0, 1, . . . , 2s − 2. The complete graph K2s+1 has an orientable triangular embedding if 2s + 1 = 12t + 3, see [15], (and we have an orientable embedding R(36t + 6|1 + 2i) for t ≥ 1 and i = 0, 1, . . . , 12t) or 2s + 1 = 12t + 7 (and we have an orientable embedding R(36t + 18|1 + 2i) for t ≥ 0 and i = 0, 1, . . . , 12t + 4). Hence, by Claim 1 and Remark 1 (we use one-hamiltonian embeddings yielded by orientable triangular embeddings of complete graphs), the theorem follows.  Theorem 2. There is a nonorientable triangular embedding of K18t + K1+2i for i = 0, 1, . . . , 6t − 2 and t ≥ 1, and of K18t +6 + K1+2i for i = 0, 1, . . . , 6t and t ≥ 1. Proof. In Section 4 we construct an orientable embedding R(6s|1 + 2i) for s ≥ 3 and i = 0, 1, . . . , 2s − 2. The complete graph K2s+1 has a nonorientable triangular embedding if 2s + 1 = 6t + 1, see [15], (and we have an orientable embedding R(18t |1 + 2i) for t ≥ 1 and i = 0, 1, . . . , 6t − 2) or 2s + 1 = 6t + 3 (and we have an orientable embedding R(18t + 6|1 + 2i) for t ≥ 1 and i = 0, 1, . . . , 6t). Hence, by Claim 1 and Remark 1 (we use one-hamiltonian embeddings yielded by nonorientable triangular embeddings of complete graphs), the theorem follows.  Theorem 3. There is a nonorientable triangular embedding of K18t −3 + Ki for i = 3, 4, . . . , 12t − 6 and t ≥ 2, and of K18t +9 + Ki for i = 3, 4, . . . , 12t + 2 and t ≥ 1. Proof. In Section 4 we construct an embedding R(6s + 3|i) for s ≥ 3 and i = 3, 4, . . . , 4s − 2. The complete graph K2s+2 has a nonorientable triangular embedding if 2s + 2 = 6t (and we have an embedding R(18t − 3|i) for t ≥ 2 and i = 3, 4, . . . , 12t − 6) or 2s + 2 = 6t + 4 (and we have an embedding R(18t + 9|i) for t ≥ 1 and i = 3, 4, . . . , 12t + 2). Hence, by Claim 1 and Remark 1 (we use one-hamiltonian embeddings yielded by nonorientable triangular embeddings of complete graphs), the theorem follows.  The constructed auxiliary embeddings R(3n|m) allow to incorporate three arbitrary triangular embeddings of Kn+1 into a triangular embedding of K3n + Km . This gives us a possibility to obtain some results on the number of nonisomorphic triangular embeddings of K3n + Km . Let K be a graph without loops and multiple edges. A t-gonal face of an embedding of K will be designated as a cyclic sequence [v1 , v2 , . . . , vt ] of vertices obtained by listing the incident vertices when traversing the boundary walk of the face in some chosen direction. The sequences [v1 , v2 , . . . , vt ] and [vt , . . . , v2 , v1 ] designate the same face. Two embeddings f and f ′ of a graph K are different labeled embeddings if f has and f ′ does not have a face [v1 , v2 , . . . , vt ]. Two embeddings f and f ′ of K are isomorphic if there is an automorphism ψ of K such that if [v1 , v2 , . . . , vt ] is a face of f , then [ψ(v1 ), ψ(v2 ), . . . , ψ(vt )] is a face of f ′ . Claim 2. Let f1 , f2 , . . . , fs be m-hamiltonian embeddings of Kt inducing the triangular embeddings ϕ1 , ϕ2 , . . . , ϕs , respectively, of Kt + Km . Then the embeddings f1 , f2 , . . . , fs are pairwise nonisomorphic if and only if the embeddings ϕ1 , ϕ2 , . . . , ϕs are pairwise nonisomorphic. Lemma 1. If there are M nonisomorphic triangular embeddings of Kn+1 and if there exists an R(3n|m), then K3n + Km has at least 1 M 3 nonisomorphic triangular embeddings. (3n)!

V.P. Korzhik / Discrete Mathematics 339 (2016) 712–720

715

Proof. For given m, since there are exactly (3n)! bijections between the vertices of K3n , it follows that each isomorphism class of the m-hamiltonian embeddings of K3n can contain at most (3n)! embeddings. Hence, taking Claim 1 into account, to 3 prove the lemma it suffices to show that  there  are at least M different labeled m-hamiltonian embeddings of K3n . Let the vertex set of R(3n|m) be A1 A2 A3 , where Ai is the vertex set of the special cycle Ci , i = 1, 2, 3. Taking Claim 2 into account, for i = 1, 2, 3, denote by Hi the set of M nonisomorphic one-hamiltonian embeddings of Kn obtained if we take  M nonisomorphic triangular embeddings of Kn+1 with vertex set {v} Ai , delete the vertex v and then relabel the vertices of every obtained one-hamiltonian embedding of Kn such that now the boundary cycle of the hamilton face is Ci . These M embeddings from Hi are different labeled embeddings, hence (a) for any two of the embeddings from Hi , one of them has and another does not have a triangular face [x, y, z ]. Now delete the interior of the (n)-gonal faces of R(3n|m). Then for i = 1, 2, 3, delete the interior of the hamilton face of an embedding from Hi and identify the boundary cycle of the hamilton face of the embedding with the special cycle   Ci . We obtain an m-hamiltonian embedding of K3n with vertex set A1 A2 A3 . Proceeding this way we can obtain M 3 m-hamiltonian embeddings of K3n which, by (a), are different labeled embeddings.  It is known (see [4]) that the number of nonisomorphic triangular embeddings of the complete graph Kn cannot exceed 2 nn / 3 . We see that in Lemma 1 the lower bound (3n1 )! M 3 does not depend on the number m of the hamilton faces of the embedding R(3n|m). This enables us to prove the following lemma. Lemma 2. Suppose that for a certain positive constant a and for an infinite set N of values of n, the number of nonisomorphic triangular embeddings of Kn is at least nan −o(n ) = 2an log2 n−o(n log2 n) as n → ∞. Then for the infinite set {3(n − 1) : n ∈ N } of values of 3(n − 1), for every m such that there exists R(3(n − 1)|m), the number of nonisomorphic m-hamiltonian embeddings 2

2

2

2

2 2 of K3(n−1) is at least (3(n − 1))(1/3)a(3(n−1)) −o((3(n−1)) ) as n → ∞.

Proof. By Lemma 1 and taking into account Stirling’s formula s! = 2s(log2 s)(1+o(1)) as s → ∞, we obtain that the number of nonisomorphic m-hamiltonian embeddings of K3(n−1) is at least 1

(3(n − 1))!

2 log n−o(n2 log n) 3 2 2

(2an

2 log n−o(n2 log n)−O(3(n−1) log (3(n−1))) 2 2 2

) = 23an

≥ 2(a/3)(3(n−1))

2 log (3(n−1))−o((3(n−1))2 log (3(n−1))) 2 2

= (3(n − 1))(1/3)a(3(n−1))

2 −o((3(n−1))2 )

as n → ∞. The proof is complete.



By a linear class of values we mean an infinite set {a + bt : t = 1, 2, . . .} of values, where a and b are integer constants. Remark 2. If in Lemma 2 the infinite set N is a linear class of values of n, then the infinite set {3(n − 1) : n ∈ N } is a linear class of values of 3(n − 1) as well. Theorem 4. There is a positive constant a such that for an infinite number of values of t, the number of nonisomorphic orientable triangular embeddings of K36t +6 + K1+2i for every i ∈ {0, 1, . . . , 12t } is at least (36t + 6)(1/3)a(36t +6) −o((36t +6) ) as t → ∞. There is a positive constant a such that for an infinite number of values of t, the number of nonisomorphic orientable triangular 2

2

2 2 embeddings of K36t +18 + K1+2i for every i ∈ {0, 1, . . . , 12t + 4} is at least (36t + 18)(1/3)a(36t +18) −o((36t +18) ) as t → ∞.

Proof. It was shown [6–8] that for i = 3, 7, there is a positive constant a such that for an infinite number of values of

n, where n ≡ i (mod 12), the number of nonisomorphic orientable triangular embeddings of Kn is at least nan −o(n ) as n → ∞ (these results were obtained for rather sparse sets of values of n; by ‘‘sparse’’ we mean that the number of suitable values not exceeding p is of order log2 p). In Section 4 we construct orientable embeddings R(36t + 6|1 + 2i) for t ≥ 1 and i = 0, 1, . . . , 12t, and R(36t + 18|1 + 2i) for t ≥ 0 and i = 0, 1, . . . , 12t + 4. Hence, by Lemma 2 and Remark 1, the theorem follows.  2

2

It was shown [4] (see also [5–9]) that, for a certain positive constant b and for an infinite number of values of n, where n ≡ 1 or 9 (mod 12), the number of nonisomorphic nonorientable triangular embeddings of Kn is at least nbn −o(n ) as n → ∞ (these results were obtained for rather sparse sets of values of n). Recently, it has been shown [9] that for i ∈ {1, 9}, for a certain positive constant b(i) and for a linear class of values of n, n ≡ i (mod 12), the number of nonisomorphic 2

2

nonorientable triangular embeddings of Kn is at least nb(i)n −o(n ) as n → ∞. In the paper [13], using index two, three, and four current graphs, a family of recursive constructions was constructed such that for any i ∈ {0, 1, 3, 4, 6, 7, 9, 10} and j ∈ {0, 1, . . . , 11}, several arbitrary nonorientable triangular embeddings of every complete graph Km , m ≡ i (mod 12), can be incorporated into a minimal nonorientable embedding of Km¯ , ¯ ≡ j (mod 12). As a consequence, using the results of [9] on i ≡ 1 or 9 (mod 12), it was shown that there is a certain m 2

2

716

V.P. Korzhik / Discrete Mathematics 339 (2016) 712–720

positive constant a such that for any i ∈ {0, 1, . . . , 11}, there is a linear class of values of n, where n ≡ i (mod 12), such that

the number of nonisomorphic minimal nonorientable embeddings of Kn is at least nan −o(n ) as n → ∞. For i ∈ {0, 1, 3, 4}, if n ≡ i (mod 12), then n ≡ i (mod 6), hence we have the following. (A) There is a positive constant a such that for i ∈ {0, 1, 3, 4}, there is a linear class of values of n, n ≡ i (mod 6), such 2

2

2 2 that the number of nonisomorphic nonorientable triangular embeddings of Kn is at least nan −o(n ) as n → ∞.

Theorem 5. There is a positive constant a such that for a linear class of values of t, the number of nonisomorphic nonorientable triangular embeddings of K18t + K1+2i for every i ∈ {0, 1, . . . , 6t − 2} is at least (18t )(1/3)a(18t ) −o((18t ) ) as t → ∞. There is a positive constant a such that for a linear class of values of t, the number of nonisomorphic nonorientable triangular 2

2

2 2 embeddings of K18t +6 + K1+2i for every i ∈ {0, 1, . . . , 6t } is at least (18t + 6)(1/3)a(18t +6) −o((18t +6) ) as t → ∞.

Proof. In Section 4 we construct (orientable) embeddings R(18t |1 + 2i) for t ≥ 1 and i = 0, 1, . . . , 6t − 2, R(18t + 6|1 + 2i) for t ≥ 1 and i = 0, 1, . . . , 6t. Hence, by Lemma 2, Remarks 1 and 2, and by (A), the theorem follows.  Theorem 6. There is a positive constant a such that for a linear class of values of t, the number of nonisomorphic nonorientable triangular embeddings of K18t −3 + Ki for every i ∈ {3, 4, 5, . . . , 12t − 6} is at least (18t − 3)(1/3)a(18t −3) −o((18t −3) ) as t → ∞. There is a positive constant a such that for a linear class of values of t, the number of nonisomorphic nonorientable triangular 2

2

2 2 embeddings of K18t +9 + Ki for every i ∈ {3, 4, 5, . . . , 12t + 2} is at least (18t + 9)(1/3)a(18t +9) −o((18t +9) ) as t → ∞.

Proof. In Section 4 we construct embeddings R(18t − 3|i) for t ≥ 2 and i = 3, 4, . . . , 12t − 6, and R(18t + 9|i) for t ≥ 1 and i = 3, 4, . . . , 12t + 2. Hence, by Lemma 2, Remarks 1 and 2, and by (A), the theorem follows.  3. Index three current graphs In this section we briefly review the theory of index three current graphs in the form used in Section 4. The reader is referred to [10,15] for more detailed development of the material sketched herein. We assume that the reader is familiar with current graphs, derived graphs and their embeddings generated by current graphs. Let G be a connected graph whose edges have all been given plus and minus directions. Hence each edge e gives rise to two reverse arcs e+ and e− of G. A rotation D of G is a permutation of the arc set A(G) of G whose orbits cyclically permute the arcs directed from each vertex. The rotation D can be represented as D = {Du : u ∈ V (G)}, where Du , called the rotation of the vertex u, is a cyclic permutation of the arcs directed from u. An edge joining vertices v and w is denoted by (v, w). An arc directed from a vertex v to a vertex w is denoted by [v, w]. For an arc a ∈ A(G), denote by θ a the reverse arc. We assume that the edges of G are assigned type 0 or 1, and that the arcs of G are also assigned type 0 or 1 such that the two arcs of any edge have the same type as the edge has. In what follows, when we refer to a graph we will always mean that the edges (and arcs) of the graph are assigned types as described above. A rotation D of G induces oriented closed walks in G called circuits. The circuits are constructed by the following wellknown tracing procedure [10,15]. 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 first 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 , . . . , ak ) is a circuit induced by D, then (θ ak , . . . , θ a2 , θ a1 ) is a circuit induced by D also, the two circuits are called reverse circuits. The set of all circuits induced by D is partitioned into pairs of reverse circuits. For a rotation D of G, by a representative set of circuits induced by D we mean a set of circuits induced by D, one from each pair of reverse circuits. The edge types and vertex rotations of G determine a cellular embedding of G in a surface such that the circuits induced by D are exactly the directed boundary walks of the faces of the embedding. Let λ be a function from the arc set of G into a group Zn such that λ(e− ) = −λ(e+ ) for every edge e of type 0 and λ(e− ) = λ(e+ ) for every edge e of type 1. The values of λ are called currents and Zn is called the current group. The triple ⟨G, λ, D⟩ where the rotation D of G induces exactly three pairs of reverse circuits is called an index three current graph. To describe a constructed index three current graph we will choose a representative set of the circuits induced by D and the circuits of the set will be called the circuits of the current graph. An index three current graph ⟨G, λ, D⟩ will be represented as a figure of G where the rotations of vertices are indicated and the circuits of the current graph are shown. The black vertices denote a clockwise rotation and the white vertices a counterclockwise rotation. In such a figure each type 0 edge is represented by one of its arcs with the current indicated. Each type 1 edge (as at the left of Fig. 1) is depicted as a broken arc with the current indicated (as at the right of Fig. 1). A circuit (a1 , a2 , . . . , at ) can be depicted as an oriented cycle passing near the arcs a1 , a2 , . . . , at in this order; this cycle is depicted as a solid (resp. dashed) line when it has normal (resp. alternative) behavior. Consider an index three current graph with current group Z3n . The circuits of the current graph are denoted (usually) by [0], [1], and [2]. The arcs of every edge of the current graph are traversed exactly twice by circuits of the current graph. Taking into account the terminology of Ringel’s book [15], by an edge ([i], δ, [j]) of the current graph we will mean an edge

V.P. Korzhik / Discrete Mathematics 339 (2016) 712–720

717

Fig. 1. A designation of a type 1 edge.

Fig. 2. An arc of an edge ([i], δ, [j]).

such that the circuits [i] and [j] traverse the arcs of the edge (if the circuit [i] traverses the arcs of the edge twice, then i = j) and in doing so the circuit [i] (resp. [j]) records the current δ (resp. −δ ) in its log. An arc of an edge ([i], δ, [j]) traversed by the circuit [i] such that the current δ is recorded in the log of the circuit is shown in Fig. 2, where in each of the two cases we indicate only how the circuit [i] traverses the first half of the arc (the arc can have type 0 or 1) and we indicate the two possibilities of how the circuit [j] can traverse the half of the arc. Note that an edge ([i], δ, [j]) is an edge ([j], −δ, [i]) as well. If (a1 , a2 , . . . , ak ) is the rotation of a vertex of a current graph ⟨G, λ, D⟩, then the element λ(a1 ) + λ(a2 ) + · · · + λ(ak ) is called the excess of the vertex. If the excess of a vertex equals zero, then we say that the vertex satisfies KCL (Kirchhoff’s Current Law). Denote by (n, ℓ) the greatest common divisor of two integers n and ℓ (this notation is similar to the notation of an edge, but in what follows it will be clear from the context what the notation means, so no confusion will arise). In Section 4 we will construct an index three current graph ⟨G, λ, D⟩ with current group Z3n satisfying the following conditions (A1)–(A6): (A1) Each vertex is trivalent or onevalent. (A2) There are three circuits: [0], [1], and [2]. (A3) There are exactly three onevalent vertices. For every i = 0, 1, 2, there is a onevalent vertex passed by the circuit [i] and having the excess ±3 when n is even, and the excess ±3 or ±6 when n is odd. (A4) Each of the trivalent vertices with nonzero excess is passed by all three circuits and has the excess ±3 when n is even, and the excess ±3 or ±6 when n is odd. (A5) The edge set of the current graph consists of 3n edges ([0], δ, [1]), ([1], δ, [2]), and ([2], δ, [0]) for δ = 1, 4, 7, . . . , 3n− 2 (these edges are not incident with onevalent vertices), and of the three edges ([i], δi , [i]), δi ∈ {3, 6}, i = 0, 1, 2 (these edges are incident with onevalent vertices). The current graph generates (see [10]) a derived embedding of a derived graph whose vertex set is the set {0, 1, . . . , 3n − 1} of all elements of Z3n . The three sets Vi (3n) = {i, i + 3, i + 6, . . . , i + 3(n − 1)}, i = 0, 1, 2, are called the vertex parts of the vertex set of the derived graph. The edge set of the derived graph is determined as follows. There is a mapping from the edge set of the derived graph onto the edge set of the current graph. Given an edge of the current graph, the edges of the derived graph mapping onto the edge are called the edges of the derived embedding induced by the edge of the current graph. An edge ([i], δ, [j]), j − i ≡ δ (mod 3), induces the edges (x, x + δ) for all x ∈ Vi (3m), where x + δ ∈ Vj (3m). Hence, (A5) implies that the edges of the current graph not incident with onevalent vertices induce the edges of the derived graph that join every two vertices from different vertex parts, and for i = 0, 1, 2, the edge incident with the onevalent vertex passed by the circuit [i] and having the excess δi induces the edges of an n-cycle Ci = (i, i + δi , i + 2δi , . . . , i + (n − 1)δi ) of the derived graph containing all n vertices of Vi (3n). We see, that the derived graph can be obtained if we take three vertex-disjoint n-cycles Ci , i = 0, 1, 2, and then join by an edge any two vertices not belonging to the same n-cycle. The face set of the derived embedding is determined as follows. There is a mapping from the face set of the derived embedding onto the vertex set of the current graph. Given a vertex of the current graph, the faces of the derived embedding mapping onto the vertex are called the faces induced by the vertex and they are determined by Theorem 4.4.1 [10] which extends to the nonorientable case as well. For an index three current graph satisfying (A1)–(A5), Theorem 4.4.1 [10] gives the following. For i = 0, 1, 2, the onevalent vertex passed by the circuit [i] and having the excess δi induces one n-gonal face bounded by the n-cycle Ci containing all n vertices od Vi (3n). The trivalent vertices satisfying KCL induce triangular faces. A trivalent vertex passed by all three circuits and having a nonzero excess induces one (3n)-gonal face incident with all 3n vertices of the derived graph. We see that if an index three current graph with current group Z3n and satisfying (A1)–(A5) has exactly m trivalent vertices with nonzero excess, then the current graph generates R(3n|m). By interchanging currents on some arcs of such a current graph we can obtain current graphs with additional number of trivalent vertices with nonzero excess, these new current graphs generate embeddings R(3n|m′ ) for m′ > m.  Two arcs [v1 , w1 ] and [v2 , w2 ] are disjoint if {v1 , w1 } {v2 , w2 } = ∅. Consider a figure of an index three current graph with current group Z3n , satisfying (A1)–(A5), having exactly m trivalent vertices with nonzero excess and thereby generating R(3n|m).

718

V.P. Korzhik / Discrete Mathematics 339 (2016) 712–720

Fig. 3. A permutation ⟨δ1 , δ2 ⟩ of the currents on two arcs of a current graph.

Fig. 4. A permutation ⟨δ1 , δ2 , δ3 ⟩ of the currents on three arcs of a current graph.

Let arcs a1 = [v1 , w1 ] and a2 = [v2 , w2 ] with currents δ1 and δ2 , respectively, be disjoint arcs of the depicted current graph such that KCL holds at v1 , w1 , v2 , w2 , and each of the four vertices is passed by all three circuits. If (δ2 − δ1 , 3n) = 3, then by a permutation ⟨δ1 , δ2 ⟩ of the currents on the arcs a1 and a2 we mean interchanging the currents on the arcs as shown in Fig. 3. Doing the permutation ⟨δ1 , δ2 ⟩, the four vertices v1 , w1 , v2 , w2 become new additional vertices with nonzero excess and if ε is the nonzero excess of any one of these vertices, then (ε, 3n) = 3, hence we obtain an index three current graph with current group Z3n , satisfying (A1)–(A5) and generating an embedding R(3n|m + 4). Let arcs a1 = [v1 , w1 ], a2 = [v2 , w2 ], and a3 = [v3 , w3 ] with currents δ1 , δ2 , and δ3 , respectively, be disjoint arcs of the depicted current graph such that KCL holds at v1 , w1 , v2 , w2 , v3 , w3 , and each of the six vertices is passed by all three circuits. If (δ2 − δ1 , 3n) = (δ3 − δ2 , 3n) = (δ1 − δ3 , 3n) = 3, then by a permutation ⟨δ1 , δ2 , δ3 ⟩ of the currents on the arcs a1 , a2 , and a3 we mean interchanging the currents on the arcs as shown in Fig. 4. Doing the permutation ⟨δ1 , δ2 , δ3 ⟩, the six vertices v1 , w1 , v2 , w2 , v3 , w3 become new additional vertices with nonzero excess and if ε is the nonzero excess of any one of these vertices, then (ε, 3n) = 3, hence we obtain an index three current graph with current group Z3n , satisfying (A1)–(A5) and generating an embedding R(3n|m + 6). Using k permutations ⟨δi , δi′ ⟩, i = 1, 2, . . . , k, where δ1 , δ1′ , δ2 , δ2′ , . . . , δk , δk′ are the currents on 2k mutually disjoint arcs of the depicted current graph, we can obtain current graphs generating R(3n|m + 4i) for i = 1, 2, . . . , k. Using a permutation ⟨ρ1 , ρ2 , ρ3 ⟩ and k permutations ⟨δi , δi′ ⟩, i = 1, 2, . . . , k, where ρ1 , ρ2 , ρ3 , δ1 , δ1′ , δ2 , δ2′ , . . . , δk , δk′ are the currents on 2k + 3 mutually disjoint arcs of the depicted current graph, we can obtain current graphs generating R(3n|m + 6 + 4i) for i = 1, 2, . . . , k. 4. Auxiliary embeddings generated by index three current graphs In this section we use index three current graphs to obtain an orientable embedding R(6s|1 + 2i) for s ≥ 3 and i = 0, 1, . . . , 2s − 2, and a nonorientable embedding R(6s + 3|i) for s ≥ 3 and i = 3, 4, . . . , 4s − 2. Fig. 5(a) shows an index three current graph with current group Z6s , generating an embedding R(6s|1), s ≥ 2. In this figure (as in what follows) the trivalent vertices with nonzero excess are marked by a star. The ends labeled by the same letter (A or B) are identified. The reader can check the properties (A1)–(A5). The embedding R(6s|1) can be used to incorporate three triangular embeddings of K2s+1 into a triangular embedding of K6s+1 . In Fig. 5(a), using i = 1, 2, . . . , s − 1 of the s − 1 permutations ⟨4, 7⟩, ⟨10, 13⟩, ⟨16, 19⟩, . . . , ⟨6s − 8, 6s − 5⟩ of the currents on vertical arcs, we can obtain current graphs generating R(6s|1 + 4i) for s ≥ 2 and i = 1, 2, . . . , s − 1. If we modify the upper left part of the current graph in Fig. 5(a) as shown in Fig. 5(b), we obtain an index three current graph with current group Z6s , generating an embedding R(6s|3), s ≥ 3. The reader can check the properties (A1)–(A5). The current graphs in Fig. 5(a) and (b) are the same to the right of the vertical arc with current 13, and it will help the reader when checking (A1)–(A5) for the current graph in Fig. 5(b). In Fig. 5(b), using the permutation ⟨3s + 2, 3s + 5⟩ of the currents (marked by a cross) on left bottom horizontal arcs and using i − 1 = 0, 1, 2, . . . , s − 3 of the s − 3 permutations ⟨16, 19⟩, ⟨22, 25⟩, . . . , ⟨6s − 8, 6s − 5⟩ of the currents on vertical arcs, we can obtain current graphs generating R(6s|3 + 4i) for s ≥ 3 and i = 1, 2, . . . , s − 2. The obtained current graphs do not have type 1 edges, so they generate orientable embeddings. Hence, we obtained an orientable embedding R(6s|1 + 2i) for s ≥ 3 and i = 0, 1, . . . , 2s − 2. Note that the current graph in Fig. 5(a) is a minor modification of the current graph given in [15, Fig. 10.2] and generating an orientable embedding R(6s|1), s ≥ 2. This modification is made in order to unify the two constructions of index three current graphs given in the present paper (Figs. 5(a) and 6(a)). Fig. 6(a) shows an index three current graph with current group Z6s+3 , generating an embedding R(6s + 3|0), s ≥ 2. The reader can check the properties (A1)–(A5). Notice that the embedding R(6s + 3|0) can be used to incorporate three triangular embeddings of K2s+2 into a triangular embedding of K6s+3 . In Fig. 6(a), using i = 1, 2, . . . , s − 1 of the s − 1 permutations ⟨4, 10⟩ and ⟨13, 16⟩, ⟨19, 22⟩, . . . , ⟨6s − 5, 6s − 2⟩ of the currents on vertical arcs, we can obtain current graphs generating R(6s + 3|4i) for s ≥ 2 and i = 1, 2, . . . , s − 1. Using

V.P. Korzhik / Discrete Mathematics 339 (2016) 712–720

719

Fig. 5. Index three current graphs generating orientable embeddings R(6s|1) and R(6s|3).

Fig. 6. Index three current graphs generating embeddings R(6s + 3|0) and R(6s + 3|3).

the permutation ⟨6s − 5, 6s − 2, 6s + 1⟩ and using i = 0, 1, 2, . . . , s − 2 of the s − 2 permutations ⟨4, 10⟩ and ⟨13, 16⟩, ⟨19, 22⟩, . . . , ⟨6s − 11, 6s − 8⟩ of the currents on vertical arcs, we can obtain current graphs generating R(6s + 3|6 + 4i) for s ≥ 3 and i = 0, 1, 2, . . . , s − 2. If we modify the upper left part of the current graph in Fig. 6(a) as shown in Fig. 6(b), we obtain an index three current graph with current group Z6s+3 , generating an embedding R(6s + 3|3), s ≥ 3. The reader can check the properties (A1)–(A5). The current graphs in Fig. 6(a) and (b) are the same to the right of the vertical arc with current 16, and it will help the reader when checking (A1)–(A5) for the current graph in Fig. 6(b).

720

V.P. Korzhik / Discrete Mathematics 339 (2016) 712–720

In Fig. 6(b), using the permutation ⟨3s − 2, 3s − 5⟩ of the currents (marked by a cross) on left bottom horizontal arcs and using i − 1 = 1, 2, . . . , s − 3 of the s − 3 permutations ⟨19, 22⟩, ⟨25, 28⟩, . . . , ⟨6s − 5, 6s − 2⟩ of the currents on vertical arcs, we can obtain current graphs generating R(6s + 3|3 + 4i) for s ≥ 3 and i = 1, 2, . . . , s − 2. Using the permutation ⟨6s−5, 6s−2, 6s+1⟩ of the currents on vertical arcs, the permutation ⟨3s−2, 3s−5⟩ of the currents (marked by a cross) on left bottom horizontal arcs and using i − 1 = 0, 1, 2, . . . , s − 4 of the s − 4 permutations ⟨19, 22⟩, ⟨25, 28⟩, . . . , ⟨6s − 11, 6s − 8⟩ of the currents on vertical arcs, we can obtain current graphs generating R(6s + 3|9 + 4i) for s ≥ 3 and i = 0, 1, . . . , s − 3. In Fig. 6(b), using the permutation ⟨10, 16⟩ of the currents on vertical arcs, we obtain a current graph generating R(6s + 3|5) for s ≥ 3. Hence, we obtained an embedding R(6s + 3|i) for s ≥ 3 and i = 3, 4, . . . , 4s − 2. It can be shown that all these embeddings R(6s + 3|i) are nonorientable. We do not do it here because (in accordance with Claim 1 and Remark 1) to obtain nonorientable triangular embeddings of K6s+3 + Ki we can use nonorientable triangular embeddings of K2s+2 . Acknowledgment The author thanks the referee for many helpful comments and suggestions. References [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

D. Craft, On the genus of joins and compositions of graphs, Discrete Math. 178 (1998) 25–50. M. Ellingham, C. Stephens, The nonorientable genus of joins of complete graphs with large edgeless graphs, J. Combin. Theory Ser. B 97 (2007) 827–845. M. Ellingham, C. Stephens, The orientable genus of some joins of complete graphs with large edgeless graphs, Discrete Math. 309 (2009) 1190–1198. M. Grannell, T. Griggs, A lower bound for the number of triangular embeddings of some complete graphs and complete regular tripartite graphs, J. Combin. Theory Ser. B 98 (2008) 637–650. M. Grannell, T. Griggs, M. Knor, On biembeddings of Latin squares, Electron. J. Combin. 16 (2009) R106, 12pp. M. Grannell, M. Knor, A lower bound for the number of orientable triangular embeddings of some complete graphs, J. Combin. Theory Ser. B 100 (2010) 216–225. M. Grannell, M. Knor, On the number of triangular embeddings of complete graphs and complete tripartite graphs, J. Graph Theory 69 (2012) 370–382. M. Grannell, M. Knor, Biembeddings of metacyclic groups and triangulations of orientable surfaces by complete graphs, Electron. J. Combin. 19 (2012) P29, 17pp. M. Grannell, M. Knor, Dihedral biembeddings and triangulations by complete and complete tripartite graphs, Graphs Combin. 29 (2013) 921–932. J. Gross, T. Tucker, Topological Graph Theory, Wiley, New York, 1987. M. Jungerman, G. Ringel, Minimal triangulations of orientable surfaces, Acta Math. 145 (1980) 121–154. V. Korzhik, Triangular embeddings of Kn − Km with unboundedly large m, Discrete Math. 190 (1998) 149–162. V. Korzhik, Recursive constructions and nonisomorphic nonorientable triangular embeddings of complete graphs, Discrete Math. 338 (2015) 2186–2196. T. McCourt, Biembedding a Steiner triple system with a hamilton cycle decomposition of the complete graph, J. Graph Theory 77 (2014) 68–87. G. Ringel, Map Color Theorem, Springer-Verlag, Berlin, 1974.