/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 14 (2018) 375-385 https://doi.org/10.26493/1855-3974.911.3b4
(Also available at http://amc-journal.eu)
A note on the directed genus of Kn n n and K
n
Rong-Xia Hao *
Department of Mathematics, Beijing Jiaotong University, Beijing 100044, P.R. China
Received 7 August 2015, accepted 28 May 2017, published online 24 October 2017
Abstract
It is proved that a complete graph Kn can have an orientation whose minimum directed genus is I" 12(n - 3)(n - 4)] if and only if n = 3,7 (mod 12). This answers a question of Bonnington et al. by using a method different from current graphs. It is also proved that a complete symmetric tripartite graph Kn n n has an orientation whose minimum directed genus is 1 (n - 1)(n - 2).
Keywords: Digraph, complete tripartite graph, directed genus, surfaces. Math. Subj. Class.: 05C10, 05B05, 05B07
1 Introduction
Throughout this paper, all graphs are assumed to be finite, connected and simple. In a directed graph D, the number of in-arcs at a vertex v is called the in-degree of v which is denoted by d- (v); the number of out-arcs at v is called the out-degree of v, denoted by d+(v). The degree of v, denoted by d(v), is the sum of d-(v) and d+(v). A digraph D is Eulerian if it is connected and every vertex has equal in-degree and out-degree. The underlying graph G of a digraph D is a graph obtained from D by suppressing all directions of the arcs in D. The orientable surface of genus h, denoted by Sh, is the sphere with h handles added. A graph is said to be 2-cell embedded in a surface S, if it is embedded in a surface S such that each component, called a region, of S \ D is homeomorphic to an open disk. A 2-cell directed embedding (or 2-cell embedding) of a digraph D on an orientable surface S means that it is a 2-cell embedding of its underlying graph of D in S such that each region is bounded by a directed cycle. In this paper, all embeddings of graphs
*The author expresses the sincere thanks to the anonymous referees for their constructive suggestions that greatly improve the quality of this paper. This work was supported by the National Natural Science Foundation of China (Nos. 11371052, 11731002), the Fundamental Research Funds for the Central Universities (Nos. 2016JBM071, 2016JBZ012) and the 111 Project of China (B16002).
E-mail address: rxhao@bjtu.edu.cn (Rong-Xia Hao)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
168
Ars Math. Contemp. 14 (2018) 267-284
and digraphs are assumed to be 2-cell embedded on oriented surfaces. Let the genus of a surface S be denoted by y(S). The directed genus (or simply say genus) of an embeddable digraph D, denoted by y(D), is the smallest of the numbers y(S) for orientable surfaces S in which D can be directed embedded. Let |X | be the cardinality of a set X.
The study of embeddings of a graph began with Euler. By now, there are many results about the genus ([14, 22, 23, 25, 26, 28, 27, 29]), the maximum genus ([24, 30]), and the genus distribution of a graph ([12, 13, 19, 20]). However, a study of the embeddings of a digraph was started in 2002 by Bonnington et al. in [2]. Bonnington, Hartsfield and Sirffl ([3]) gave some obstructions for directed embeddings of digraphs and proved Kuratowski-type theorem for embeddings of digraphs in the plane. This area has remained almost uninvestigated. As we know, genera of only a few kinds of digraphs are known. Hales and Hartsfield calculated the directed genus of the de Bruijn graph in [15]. Hao et al. ([16, 17, 18]) obtained the embedding distributions of some digraphs and maximum embedding properties of digraphs. Chen, Gross and Hu ([4]) derived a splitting theorem for digraph embedding distributions that is analogous to the splitting theorems of [11] and [5] for graph embedding distributions.
Let y(G) denote the genus of a graph G. There are many results on computing genera of undirected graphs. For example, in [25], the genera of the complete graph K„ and the complete tripartite graph Km„,„,„ were given as follows: y(K„) = [yg-(n - 3)(n - 4)] and y(Kmninin) = 1 (mn - 2)(n - 1). In [28], y(K„,„,„-2) = 2. (n - 2)2 for even n > 2 and y(K2„,2„,„) = 2(3n - 2)(n - 1) for n > 1 were derived. In [26], y(K„,„,„) = J(n - 2)(n - 1) was obtained.
Up to now, the genera of only a few kinds of digraphs are known. For examples, the directed genus of the de Bruijn graph was derived in [15]. In [2], Bonnington et al. determined the genera of the cartesian product C„ x C„ of two directed cycles, the spoke digraph on n = 2k +1 vertices and the directed antiprism DAk, which are (n2 - 3n + 2)/2, k - 1 and 0, respectively. Let K„ and K„,„,„ be directed graphs gotten from the complete graph K„ and the complete tripartite K„,„,„, respectively, by giving an orientation to each edge. In this paper, we aim to answer the following problem by using a method different from current graphs.
Problem 1.1 ([2]). Whichkindsof K„ have y(G ) = [ ^ (n - 3)(n - 4)], the genus of K„.
A natural question analogue to Problem 1.1 is the following.
Problem 1.2. Which kinds of K„,„,„ with n vertices in each parts have directed genus
2(n - 1)(n - 2), the genus of K„,„,„.
In this paper, we solve the Problems 1.1 and 1.2. Problem 1.2 is solved by giving the equivalent conditions for the minimum directed genus embedding of a directed graph K„,„,„ and a pair of biembeddable Latin squares with order n in an orientable surface. Furthermore, we prove that there is a one to one correspondence between the set of directed embeddings of a digraph D and the set of face-2-colorable embeddings of the underlying graph of D both on orientable surfaces. The result that there exists an orientation on edges of K„ such that the obtained tournament K„ has the directed genus [yy (n - 3)(n - 4)], when n = 3, 7 (mod 12) is gotten which answer the Problem 1.1.
R.-X. Hao: A note on the directed genus of K„,„,„ and Kn	377
2 Alternating rotations, face-2-colorable embeddings, and Latin squares
An alternating rotation at a vertex v of D is a cyclic permutation of the arcs incident at v, such that in-arcs alternate with out-arcs. A list of alternating rotations, one for each vertex, is called an alternating embedding scheme (also called alternating rotation system) for the digraph D. There exists a one to one correspondence between the set of all embeddings (resp. directed embeddings) of a graph G (resp. a digraph D) on orientable surfaces and the set of the embedding schemes (resp. alternating embedding schemes) of G (resp. D). A color class is a set of faces with the same color. A face-2-colorable embedding of a graph G is an embedding which admits a 2-coloring of regions such that no two distinct regions of the same color shares a common edge. Two colors always mean black and white. Regions in an embedding of a graph are also called faces, while regions in a directed embedding of a digraph are partitioned into faces which use the arcs in the forward direction and antifaces which use arcs traversed against the given orientation.
An embedding is triangular if all regions are bounded by 3-cycles. Two face-2-colorable embeddings of Kn are said to be isomorphic if there exists a permutation on the n vertices (of the complete graph) such that it maps edges and faces of one embedding to edges and faces of the other one, respectively, see [2]. Equivalently, two face-2-colorable embeddings of Kn are isomorphic if and only if there exists a permutation on the n vertices such that it either preserves the color of the triangles or reverses the color. Let Di and D2 be two digraphs. If D1 is derived from D2 by reversing all arcs of D2, then we say these two digraphs have the opposite orientation.
A transversal design TD(3, n) is an ordered triple (V, G, B), where V is a 3n-element set (the points), G is a partition of V into three disjoint sets (the groups) each of which has cardinality n, and B is a set of three-element subsets of V (the triples), such that every unordered pair of elements from V is either contained in precisely one triple or one group, but not both.
Example 2.1. An example of a TD(3, n) of n = 3. Let
V = {1, 2, 3,..., 9},
G = {{4,5,6}, {7,8,9}, {1,2, 3}}, and
B = {(4, 7, 3), (4, 8,1), (4, 9, 2), (5, 7,1), (5, 8, 2), (5, 9, 3), (6, 7, 2), (6, 8, 3), (6, 9,1)}. Then (V, G, B) is a transversal design TD(3,3).
A Latin square LS(n) of order n is an n x n array filled with n different entries, each occurring exactly once in each row and exactly once in each column.
Example 2.2. A Latin square LS(n) of order n for n = 3. Let
M =
3 1 2
1	2 3
2	3 1
Then M is a Latin square LS(3).
There are relations among the face-2-colorable triangular embeddings of Kn,n,n on an orientable surface, the transversal design TD(3, n) and the Latin squares as follows.
170
Ars Math. Contemp. 14 (2018) 267-284
For a given face 2-colourable triangular embeddings of Kn,n,n on an orientable surface, it is proved in [10] that there exists a transversal design which is determined under one of the clockwise and counter-clockwise in each colour class. On the other hand, for a given transversal design TD(3, n) = (V, G, B), there is a Latin square determined by TD(3, n) by assigning the three groups in G as labels for the row, columns and entries of the Latin square.
Two color classes A and B of a face-2-colorable triangular embedding of Kn n n on an orientable surface give two Latin squares, corresponding to A and B respectively, which is considered as a biembedding of these two Latin squares with order n. Two Latin squares A and B are biembeddable, denoted by A ixi B, on an orientable surface S if there is a face-2-colorable (black and white) triangular embedding of Kn n n in the orientable surface S such that the white face set is A and the black face set is B. For more details, the readers are referred to [6, 7, 8, 9] and [21].
Example 2.3. Let Vi, V2 and V3 be a partition of V(K3,3,3), where V = {4, 5,6}, V2 = {7, 8,9} and V3 = {1, 2, 3}. For a given embedding p of K3 3 3 on an orientable surface, let pv be the rotation at a vertex v. Let
p1 = (7, 5, 9, 6, 8,4); p2 = (7, 6, 9,4, 8, 5); p3 = (7,4, 9, 5, 8, 6); p4 = (7, 3, 9, 2, 8, l); p5 = (7,1, 9, 3, 8, 2); p6 = (8, 3, 7, 2, 9, l); p7 = (l, 5, 2, 6, 3,4); p8 = (2, 5, 3, 6,1, 4); p9 = (2,4, 3, 5,1, 6).
Then p = {p4 : i e {1,..., 9}} is a face 2-colourable triangular embedding of K3,3,3 on an orientable surface. In fact, a set of faces with the white color is
A1 = {(5, 7,1), (6, 9,1), (4, 8,1), (6, 7, 2), (4, 9, 2), (5, 8, 2), (4, 7, 3), (5, 9, 3), (6, 8, 3)};
while a set of faces with the black color is
A2 = {(9, 5,1), (8, 6,1), (7, 4,1), (9, 6, 2), (8,4, 2), (7, 5, 2), (9,4, 3), (8, 5, 3), (7, 6, 3)}.
There exists a transversal design TD(3,3), say (V, G, B1), which is determined under the clockwise in white colour class A1. That is,
V	= {1, 2, 3,..., 9},
G = {{4,5, 6}, {7, 8, 9}, {1, 2, 3}}, and
B1 = {(5, 7,1), (6, 9,1), (4, 8,1), (6, 7, 2), (4, 9, 2), (5, 8, 2), (4, 7, 3), (5, 9, 3), (6, 8, 3)}.
There exists another transversal design TD(3, 3), say (V, G, B2), which is determined under the counter-clockwise in black colour class A2. That is,
V	= {1, 2, 3,..., 9},
G = {{4,5, 6}, {7, 8, 9}, {1, 2, 3}}, and
B2 = {(5, 9,1), (6, 8,1), (4, 7,1), (6, 9, 2), (4, 8, 2), (5, 7, 2), (4, 9, 3), (5, 8, 3), (6, 7, 3)}.
Example 2.4. Let (V, G, B1) be a transversal design given in Example 2.3. Assume that {4, 5,6} labels for the row, {7,8, 9} labels for columns and {1,2,3} labels for entries of the Latin square. Thus
B1 = {(5, 7,1), (6, 9,1), (4, 8,1), (6, 7, 2), (4, 9, 2), (5, 8, 2), (4, 7, 3), (5, 9, 3), (6, 8, 3)}
R.-X. Hao: A note on the directed genus of K„,„,„ and Kn
377
determines the matrix A1 as
7 8 9 '3 1 2N 1 2 3 231
(2.1)
Thus there is a Latin square Ai determined by (V, G, B1), where
Ai
312 123 231
Similarly, for a transversal designs (V, G, B2) given in Example 2.3, there is a Latin square A2 determined by (V, G, B2), where
A2
123 231 312
In fact, using V1 = {4,5,6} as labels for the row, V2 = {7, 8,9} as labels for the columns, and V3 = {1,2, 3} as labels for entries of the Latin square, thus
B2 = {(5, 9,1), (6, 8,1), (4, 7,1), (6, 9, 2), (4, 8, 2), (5, 7, 2), (4, 9, 3), (5, 8, 3), (6, 7, 3)}
determines the matrix A2 as
7 8 9 4/1 2 3\
5	I 2 3 1 I .	(2.2)
6	y3 1 2/
As a result, a face-2-colorable triangular embedding p of K3 3 3 on an orientable surface gives two Latin squares A1 and A2, corresponding to two color classes A1 and A2 respectively. And A1 ix A2 is a biembedding of these two Latin squares with order 3.
Because an embedding of an embeddable digraph is an embedding of the underlying graph, the following version of Euler's polyhedral formula holds.
Lemma 2.5. Let D = (V, A) be an embedding digraph, then for any alternating embedding scheme p of D, we have
|V| — |A| + |R| = 2 - 2g,
where |R| is the number of regions in the embeding scheme p and g is the genus of the embedding surface.
Lemma 2.6 ([7]). There is a unique regular triangular embedding of a complete tripartite graph Kn,n,n on an orientable surface for n > 2.
Lemma 2.7 ([6]). For a triangular embedding of Kn,n,n, it is orientable if and only if it is face-2-colorable embedding.
The readers are referred to [1] for any undefined notations.
172
Ars Math. Contemp. 14 (2018) 267-284
___ —*
3 The directed genus of Kn,n,n
For an embedding a of a given digraph Kn,n,n, the alternating embedding scheme is denoted by pCT, the alternating rotation at a vertex v e V(D) is denoted by pCT(v) (or simply Pv ).
Recall that Kn,n,n is a complete tripartite graph. A complete tripartite digraph, denoted by Kn,n,n, obtained from Kn,n,n by giving an orientation for each edge in Kn,n,n. In the following, we find an orientation Kn,n,n of Kn,n,n such that Kn,n,n has the directed genus
1 (n - 1)(n - 2), the same as the genus of Kn,n,n.
Theorem 3.1. The following two conditions on an orientation Kn,n,n of the complete tripartite graph Kn,n,n are equivalent:
(1)	Kn,n,n has a directed embedding on the orientable surface of genus 2 (n — 1)(n — 2), for which we call the sets of faces and antifaces A and B, respectively.
(2)	The sets A and B of white faces and black faces for a face-2-colorable triangular embedding of Kn,n,n correspond to a pair of biembeddable Latin squares A and B of order n.
Proof. We first show that (1) implies (2).
Assume Kn,n,n has a directed embedding on an orientable surface of genus 1 (n — 1)(n—2) such that the sets of faces and antifaces A and B, respectively. Let ^: Kn,n,n ^ S be this directed embedding of Kn,n,n and p^ be the alternating embedding scheme of Note that Kn,n,n has 3n vertices, 3n2 arcs and the embedding genus 2 (n — 1)(n — 2). By Euler's formula of Lemma 2.5, the number of regions in p^ is 2n2. This implies that each region is bounded by a directed 3-cycle because there are no ¿-cycles for i = 1,2.
Let the embedding scheme p of Kn,n,n be the same as p^ without considering the directions of arcs, then Au B is the facial set of the embedding p of Kn,n,n. We color faces in A with white and antifaces in B with black. By the definition of a directed embedding, each arc appears once in exactly one facial boundary and exactly one antifacial boundary. That is, no two distinct faces in A (resp. B) are incident to the same edge. So p of Kn,n,n is a face-2-colorable triangle embedding with two color classes A and B with |A| = |B| = n2. Note that two color classes A and B of a face-2-colorable triangular embedding of Kn,n,n on an orientable surface give two Latin squares, say A and B, corresponding to A and B respectively, which is a biembedding of these two Latin squares A and B. The result (2) is obtained.
Secondly, we show that (2) implies (1).
Suppose (2) holds. Note that there exists a face-2-colorable triangular embedding, say of Kn,n,n on an orientable surface with two facial color classes A and B which corresponds a pair of biembeddable Latin squares A and B of order n, respectively. Assume the embedding scheme of the embedding ^ is p^ and the rotation at vertex v in K„,„,„ is denoted by p^(v). Let V(K„,„,„) = Vi U V2 U V3, where {Vl, V2, V3} is a partition of V(Kn,n,n). Suppose Vl = {aL, a2,..., a„|, V2 = {bL, b2,..., bn} and V3 = {ci ,C2 ,...,C„|.
Note that A and B determine transversal designs (V, G, A) and (V, G, B) respectively, where V = V(Kn,n,n), G = {Vl, V2, V3| and the faces in each color class form the triples in A and B of the transversal designs.
R.-X. Hao: A note on the directed genus of K„,„,„ and Kn	377
For every edge uv e E(Kn,n,n), without loss of generality, let u = aj e V1, v = bj e V2. By the definition of a transversal design, there is only one triple in A containing aj, bj, say {aj, bj, cx} for some cx G V3. Thus, vertices bj and cx are neighbors of a^ Without loss of generality, let cx be the closest successor of bj in the rotation p^(aj) along the counter-clockwise and the color of the region corresponding to the triple {aj, bj, cx} be white. On the other hand, there is exactly one triple in B containing aj, bj, say {aj, bj ,cy } with cy G V3, so bj is the closest successor of cy in the rotation p^(aj) along the counterclockwise and the color of the region corresponding to the triple {aj, bj, cy } is black which is illustrated in the left one of Figure 1.
Figure 1: The rotations at vertices aj and w respectively.
Give the orientation of the edge uv = ajbj from u = aj to v = bj, i.e., the color of the left region of the arc uv is white and the color of the right region is black. By the random choice of uv, all edges in Kn,n,n are oriented and the obtained digraph is Kn,n,n.
In the following, we only need to show that this orientation makes the in-arcs and out-arcs alternating at p^(v) for any v e V(Kn,n,n). By the contrary, suppose there exists a vertex, say w e V, such that in-arcs and out-arcs at w are not alternative. Without loss of generality, suppose two arcs, say ui W, u2 W, are two neighbor in-arcs of w in p^(w) and P0(w) = (..., u1, u2,...) along counter-clockwise. Let the left face and right face of uiw going from u1 to w be F1 and F2 respectively and the left face and right face of u2 w going along the direction from u2 to w be F3 and F4 respectively. Then F2 = F3. By the principle of the orientation, F2 is colored black because of the direction of arc u 1 w and F3 is colored white because of the direction of arc u2 w, which is shown in the right graph of Figure 1. It contradicts with face-2-colorable because F2 = F3. As a result, this orientation makes in-arcs and out-arcs alternating at every vertex w e V along the rotation p^(w).
As a result, Kn,n,n, obtained from Kn n n by this orientation, has an alternating embedding scheme determined by ^ such that the sets of faces and antifaces of this directed embedding of Kn,n,n are A and B, respectively.
Since each region of this directed embedding of Kn n n is a 3-cycle, the number of regions is 2n2. By |V| = 3n, the cardinality of arcs in Kn n n being 3n2 and Lemma 2.5, it follows 3n - 3n2 + 2n2 = 2 - 2g, where g is the genus of this directed embedding. So g = 2 (n - 1)(n - 2). Since neither loop nor 2-cycle is in Kn,n,n, the minimum directed genus of KKn,n,n is 2 (n- 1)(n-2). Thus KKn,n,n has a directed embedding in the orientable surface of genus 1 (n - 1)(n - 2), for which we call the sets of faces and antifaces A and
174
Ars Math. Contemp. 14 (2018) 267-284
B, respectively.	□
Theorem 3.2. Let Kn,n,n be the complete tripartite graph. Then there exists an orientation of Kn,n,n such that the obtained digraph Kn,n,n has the directed genus 2(n — 1 )(n — 2), the same as the genus of Kn,n,n.
Proof. Let Kn,n,n be the digraph obtained from Kn,n,n by giving the orientation to each edge in Kn,n,n and g be the directed genus of Kn,n,n.
(1)	If n =1, then Kn,n,n = Ki,i,i is a triangle. Let Ki,i,i be the digraph obtained by giving an orientation of Ki,i,i such that it is a directed 3-cycle. Hence g = 0.
(2)	If n > 2, by Lemma 2.6, there is a unique regular triangular embedding of a complete tripartite graph Kn,n,n on an orientable surface. By Lemma 2.7, this regular triangular embedding of a complete tripartite graph Kn,n,n must be a face-2-colorable embedding and two set of color faces are denoted by A and B respectively. By Theorem 3.1 , there is an orientation for Kn,n,n such that the resulting digraph Kn,n,n has a directed embedding in the orientable surface of genus i (n — 1)(n — 2), the set of faces is A and the set of antifaces is B. Thus the result holds.	□
4 The number of different orientations of Kn
Theorem 3.1 for a directed triangular embedding of the directed complete tripartite graph can be generalized to Lemma 4.1 for directed embedding of a general digraph.
Lemma 4.1. The following two conditions on an orientation G of a graph G are equivalent.
(1)	G has a directed embedding on an orientable surface of genus g.
(2)	G has a face-2-colorable embedding on an orientable surface of genus g.
Proof. We first show that (1) implies (2).
Let G = (V, E) be a graph with n vertices, G = (V, A) be a digraph obtained from G by giving an orientation to each edge. So |V| = n and |E| = |A|. By (1), G has a directed embedding on an orientable surface of genus g. Let p be the alternating embedding scheme and Fi and F2 be the set of faces and antifaces in G, respectively. Note that a directed embedding of G is an embedding of G and Fi U F2 is the set of faces of this embedding of G. We color regions in Fi with white and rigions in F2 with black. From the definition of directed embedding, each arc in GK is incident to exactly one face and exactly one antiface in the directed embedding p of GK, so there is no two distinct regions of the same color sharing a common edge in this embedding of G. It implies that this embedding of G is the face-2-colorable embedding on an orientable surface with genus g. So condition (2) holds.
Secondly, we show that (2) implies (1).
Suppose that (2) holds. Let p be the embedding scheme of a face-2-colorable embedding of a graph G = (V, E) on an orientable surface S of genus g. And all regions of the embedding p can be colored by white and black. Let Fi and F2 be the set of white and black regions, respectively. For each edge e G E(G), there are exactly two regions sharing the edge e, denoted by Fei and Fe2. By the definition of the face-2-colorable embedding, Fei and Fe2 have different colors. Without loss of generality, suppose that F^ G Fi and F2 G F2. We give the orientation of e such that the left is white region Fei and the right is black region Fe2 (this is known as orientationalprinciple). Since each edge can be oriented,
R.-X. Hao: A note on the directed genus of K„,„,„ and Kn	377
one can obtain a digraph, denoted by G, from the graph G by this orientational principle. Let the alternating embedding scheme of G be the same as p. By the orientational principle and face-2-colorability, the in-arcs and out-arcs alternate at each vertex in p of G. Thus this embedding scheme is an alternating embedding scheme of G as a directed embedding in the same surface S with genus g, so condition (1) holds.	□
Theorem 4.2. There is a one to one correspondence between the set of directed embeddings of a digraph D on orientable surfaces and the set of face-2-colorable embeddings of the underlying graph of D on orientable surfaces.
Proof. Let D be a digraph and the underlying graph of D be obtained from D by ignoring the direction of arcs. Theorem 4.2 is obtained directly from Lemma 4.1.	□
The following Theorem 4.3 give an answer to the problem in [2].
Theorem 4.3. If n = 3,7 (mod 12), then there exists an orientation on edges of Kn such that the obtained tournament Kn has directed genus \^ (n — 3)(n — 4)].
Proof. From Ringel and Youngs' results in [25] and [31], if n = 3,7 (mod 12), there exists a face-2-colorable triangular embedding of Kn on an orientable surface. By Lemma 4.1, there exists an orientation on edges of Kn such that the obtained digraph Kn has a directed triangular embedding on an orientable surface. By Euler's formula, digraph Kn has directed genus \ 12 (n — 3)(n — 4)].	□
5 Concluding remarks
In this paper, we show that there is a one to one correspondence between the set of directed embeddings of a digraph D and the set of face-2-colorable embeddings of the underlying graph of D on orientable surfaces. Furthermore, we show that there exist orientations on Kn,n,n and Kn such that the obtained graph Kn,n,n has the directed genus 2 (n — 1)(n — 2) for n > 1 and Kn has directed genus \ 12 (n — 3)(n — 4)] for n = 3,7 (mod 12) which answers the problem about tournaments given in [2] by using a method different from current graphs which were discussed by the same author et al.
References
[1]	J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Elsevier, New York, 1976.
[2]	C. P. Bonnington, M. Conder, M. Morton and P. McKenna, Embedding digraphs on orientable surfaces, J. Comb. Theory Ser. B 85 (2002), 1-20, doi:10.1006/jctb.2001.2085.
[3]	C. P. Bonnington, N. Hartsfield and J. Siran, Obstructions to directed embeddings of Eulerian digraphs in the plane, European J. Combin. 25 (2004), 877-891, doi:10.1016/j.ejc.2003.06.006.
[4]	Y. Chen, J. L. Gross and X. Hu, Enumeration of digraph embeddings, European J. Combin. 36 (2014), 660-678, doi:10.1016/j.ejc.2013.10.003.
[5]	Y. Chen, T. Mansour and Q. Zou, Embedding distributions of generalized fan graphs, Canad. Math. Bull. 56 (2013), 265-271, doi:10.4153/cmb-2011-176-6.
[6]	M. J. Grannell, T. S. Griggs and M. Knor, Biembeddings of Latin squares and Hamiltonian decompositions, Glasgow Math. J. 46 (2004), 443-457, doi:10.1017/s0017089504001922.
176
Ars Math. Contemp. 14 (2018) 267-284
[7]	M. J. Grannell, T. S. Griggs, M. Knor and J. Sirân, Triangulations of orientable surfaces by complete tripartite graphs, Discrete Math. 306 (2006), 600-606, doi:10.1016/j.disc.2005.10. 025.
[8]	M. J. Grannell and M. Knor, A lower bound for the number of orientable triangular embeddings of some complete graphs, J. Comb. Theory Ser. B 100 (2010), 216-225, doi:10.1016/j.jctb. 2009.08.001.
[9]	M. J. Grannell and M. Knor, A construction for biembeddings of Latin squares, Electron. J. Combin. 18 (2011), #P190, http://www.combinatorics.org/ojs/index.php/ eljc/article/view/v18i1p19 0.
[10]	M. J. Grannell and M. Knor, Dihedral biembeddings and triangulations by complete and complete tripartite graphs, Graphs Combin. 29 (2013), 921-932, doi:10.1007/s00373-012-1163-1.
[11]	J. L. Gross, Genus distribution of graphs under surgery: adding edges and splitting vertices, New York J. Math. 16 (2010), 161-178, http://nyjm.albany.edu/j/2010/16_ 161.html.
[12]	J. L. Gross and M. L. Furst, Hierarchy for imbedding-distribution invariants of a graph, J. Graph Theory 11 (1987), 205-220, doi:10.1002/jgt.3190110211.
[13]	J. L. Gross, D. P. Robbins and T. W. Tucker, Genus distributions for bouquets of circles, J. Comb. Theory Ser. B 47 (1989), 292-306, doi:10.1016/0095-8956(89)90030-0.
[14]	J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1987.
[15]	A. W. Hales and N. Hartsfield, The directed genus of the de Bruijn graph, Discrete Math. 309 (2009), 5259-5263, doi:10.1016/j.disc.2007.11.003.
[16]	R.-X. Hao and Y.-P. Liu, The genus distributions of directed antiladders in orientable surfaces, Appl. Math. Lett. 21 (2008), 161-164, doi:10.1016/j.aml.2007.05.001.
[17]	R.-X. Hao and Y.-P. Liu, The genus polynomials of cross-ladder digraphs in orientable surfaces, Sci. China Ser. a 51 (2008), 889-896, doi:10.1007/s11425-007-0125-1.
[18]	R.-X. Hao, L.-S. Xu, X.-K. Li and J.-G. Zhang, Embeddable properties of digraphs in orientable surfaces, Acta Math. Appl. Sin. 31 (2008), 630-634.
[19]	J. H. Kwak and J. Lee, Genus polynomials of dipoles, KyungpookMath. J. 33 (1993), 115-125, http://pdf.medrang.co.kr/kmj/33/kmj0 33-01-14.pdf.
[20]	J. H. Kwak and S. H. Shim, Total embedding distributions for bouquets of circles, Discrete Math. 248 (2002), 93-108, doi:10.1016/s0012-365x(01)00187-x.
[21]	J. G. Lefevre, D. M. Donovan, M. J. Grannell and T. S. Griggs, A constraint on the biembedding of Latin squares, European J. Combin. 30 (2009), 380-386, doi:10.1016/j.ejc.2008.05.007.
[22]	Y.-P. Liu, Embeddability in Graphs, volume 338 of Mathematics and its Applications, Kluwer Academic Publishers, Dordrecht, 1995.
[23]	B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, Maryland, 2001.
[24]	E. A. Nordhaus, B. M. Stewart and A. T. White, On the maximum genus of a graph, J. Comb. Theory Ser. B 11 (1971), 258-267, doi:10.1016/0095-8956(71)90036-0.
[25]	G. Ringel, Map Color Theorem, volume 209 of Grundlehren der mathematischen Wissenschaften, Springer-Verlag, Berlin, 1974, doi:10.1007/978-3-642-65759-7.
[26]	G. Ringel and J. W. T. Youngs, Das Geschlecht des vollstandigen dreifarbbaren Graphen, Comment. Math. Helv. 45 (1970), 152-158, doi:10.1007/bf02567322.
R.-X. Hao: A note on the directed genus of K„,„,„ and Kn	377
[27]	S. Stahl, Permutation-partition pairs II: bounds on the genus of the amalgamation of graphs, Trans. Amer. Math Soc. 271 (1982), 175-182, doi:10.2307/1998757.
[28]	S. Stahl and A. T. White, Genus embeddings for some complete tripartite graphs, Discrete Math. 14 (1976), 279-296, doi:10.1016/0012-365x(76)90042-x.
[29]	C. Thomassen, The graph genus problem is NP-complete, J. Algorithms 10 (1989), 568-576, doi:10.1016/0196-6774(89)90006-0.
[30]	N. H. Xuong, How to determine the maximum genus of a graph, J. Comb. Theory Ser. B 26 (1979), 217-225, doi:10.1016/0095-8956(79)90058-3.
[31]	J. W. T. Youngs, The mystery of the Heawood conjecture, in: B. Harris (ed.), Graph Theory and its Applications, Academic Press, New York, pp. 17-50,1970, proceedings of an Advanced Seminar (Mathematics Research Center, University of Wisconsin, Madison, Wisconsin, 1969).