¿^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 339-357 https://doi.org/10.26493/1855-3974.1998.2f4
(Also available at http://amc-journal.eu)
The thickness of the Kronecker product
of graphs*
Xia Guo ©
School of Mathematical Sciences, Xiamen University, Xiamen, P. R. China
Yan Yang t©
School of Mathematics, Tianjin University, Tianjin, P. R. China
Received 7 May 2019, accepted 10 May 2020, published online 22 October 2020
Abstract
The thickness of a graph G is the minimum number of planar subgraphs whose union is G. In this paper, we present sharp lower and upper bounds for the thickness of the Kronecker product G x H of two graphs G and H. We also give the exact thickness numbers for the Kronecker product graphs Kn x K2, Km,n x K2 and Kn,n,n x K2.
Keywords: Thickness, Kronecker product graph, planar decomposition. Math. Subj. Class. (2020): 05C10
1 Introduction
The thickness 6(G) of a graph G is the minimum number of planar subgraphs whose union is G. It is a measurement of the planarity of a graph, the graph with 6(G) = 1 is a planar graph; it also has important application in VLSI design [15]. Since W. T. Tutte [16] inaugurated the thickness problem in 1963, the thickness of some classic types of graphs have been obtained by various authors, such as [1, 3, 4, 13, 17, 19] etc. In recent years, some authors focus on the thickness of the graphs which are obtained by operating on two graphs, such as the Cartesian product graph [8, 20] and join graph [7]. In this paper, we are concerned with the Kronecker product graph.
* Supported by the National Natural Science Foundation of China under Grant No. 11401430. The authors are grateful to Bojan Mohar for helpful comments after the second author gave a talk on this topic in Beijing, March 2019. Especially, Bojan Mohar helped us to state the upper bound in Theorem 2.1 in an improved form. The authors also thank the referees for their helpful comments and suggestions. t Corresponding author.
E-mail addresses: guoxia@stu.xmu.edu.cn (Xia Guo), yanyang@tju.edu.cn (Yan Yang)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
339	Ars Math. Contemp. 18 (2020) 187-210
The Kronecker product (also called as tensor product, direct product, categorical product) G x H of graphs G and H is the graph whose vertex set is V(G x H) = V(G) x V(H) and edge set is E(G x H) = {(g, h)(g', h') | gg' e E(G) and hh' e E(H)}. Figure 1 shows the Kronecker product graph K5 x K2 in which {ui,..., u5} and {vi,v2} are the vertex sets of the complete graphs K5 and K2, respectively. Many authors did research on various topics of the Kronecker product graph, such as for its planarity [2, 10], connectivity [18], coloring [9, 12] and application [14] etc.
(U1,V2) (U2,V2) (U3.V2) (u4,V2) (U5.V2)
(ui,Vl) (u2,Vl) (u3,Vl) (u4,Vl) (u5,Vl)
Figure 1: The Kronecker product graph K5 x K2.
The complete graph Kn is the graph on n vertices in which any two vertices are adjacent. The complete bipartite graph Km,n is the graph whose vertex set can be partitioned into two parts X and Y, |X | = m and |Y| = n, every edge has its ends in different parts and every two vertices in different parts are adjacent. The complete tripartite graph Kl,mn is defined analogously.
In this paper, we present lower and upper bounds for the thickness of the Kronecker product of two graphs in Section 2, in which the lower bound comes from Euler's formula and the upper bound is derived from the structure of the Kronecker product graph. Then we study the thickness of the Kronecker product of a graph with K2. There are two reasons why we interested in it. One reason is that the upper bound for the thickness of the Kronecker product of two graphs we will provide relies on that of the Kronecker product of a graph with K2. Another reason is that the planarity of the Kronecker product of two graphs have been characterized in [10], but a graph with K2 is one of its missing cases. It's a difficult case, because there exist non-planar graphs whose Kronecker product with K2 are planar graphs, see Figures 1 and 2 in [2] for example. In Sections 3 and 4, we provide the exact thickness numbers for the Kronecker product graphs Kn x K2, Km n x K2 and
Kn,n,n x K2.
For undefined terminology, see [5].
2 Thickness of the Kronecker product graph G x H
A k-edge-coloring of a graph G is a mapping f: E(G) ^ S, where S is a set of k colors. A k-edge-coloring is proper if incident edges have different colors. A graph is k-edge-colorable if it has a proper k-edge-coloring. The edge chromatic number x'(G) of a graph G is the least k such that G is k-edge-colorable.
Theorem 2.1. Let G and H be two simple graphs on at least two vertices, then 2|E (G)||E (H ^
3|V(G)||V(H)|- 6
< 6(G x H) < min{x'(H)6(G x K2), x'(G)6(H x K2)},
in which x'(H) and x'(G) are edge chromatic number of H and G respectively.
X. Guo and Y. Yang: The thickness of the Kronecker product of graphs
351
Proof. It is easy to observe that the number of edges in G x H is |E(G x H)| = 2|E(G)||E(H)| and the number of vertices in G x H is |V(G x H)| = |V(G)||V(H)|. From the Euler's Formula, the planar graph with |V(G)||V(H)| vertices, has at most 3|V(G) || V(H) | - 6 edges, the lower bound follows.
The x'(H)-edge-coloring of H can be seen as a partition {Mi,..., Mx>(H)} of E(H), in which Mi denotes the set of edges assigned color i (1 < i < x'(H)). Then Mi is a matching and E(H) = Mi U • • • U MX/(H). Because G x H = uX=l(1ff)(G x Mi) and 0(G x Mj) = 0(G x K2), we have 0(G x H) < x'(H)0(G x K2). With the same argument, we have 0(G x H) < x'(G)0(H x K2). The upper bound can be derived.	□
In the following, we will give examples to show both the lower and upper bound in Theorem 2.1 are sharp. Let G and H be the graphs as shown in Figure 2(a) and (b) respectively. Figure 2(c) illustrates a planar embedding of the graph G x {v1v2}, in which we denote the vertex (ui,vj) by uj, 1 < i < 7, 1 < j < 2. So the thickness of G x {v1 v2} is one which meets the lower bound in Theorem 2.1. Figure 2(d) illustrates a planar embedding of the graph G x {v2v3} which is isomorphic to G x {v1v2}. Because G x H = G x {v1 v2} U G x {v2v3}, we get a planar subgraph decomposition of G x H with two subgraphs, which shows the thickness of G x H is not more than two. On the other hand, the graph G x H contains a subdivision of K5 which is exhibited in Figure 2(e), so G x H is not a planar graph, its thickness is greater than one. Therefore, the thickness of G x H is two which meets the upper bound in Theorem 2.1.
(c) The graph G x {viv2}.	(d) The graph G x {^2^3}.
Figure 2: An example to show both lower and upper bounds in Theorem 2.1 are sharp.
152
Ars Math. Contemp. 18 (2020) 187-210
Figure 2: An example to show both lower and upper bounds in Theorem 2.1 are sharp.
The graph GxH has a triangle if and only if both G and H have triangles. If GxH does not contain any triangles, from the Euler's Formula, the planar graph with |V(G)||V(H)| vertices, has at most 2| V(G) ||V(H) | - 4 edges, a tighter lower bound can be derived.
Theorem 2.2. Let G and H be two simple graphs on at least two vertices. If G x H does not contain any triangles, then
|E(G)||E(H )|
< 0(G x H) < min{x'(H)0(G x K2),x'(G)0(H x K2)}.
|V(G)||V(H)|- 2 3 The thickness of Kn x K2 and Km,n x K2
In this section, by making use of the thickness number of Kn n and a known planar decomposition of Kn n as shown in Lemmas 3.1 and 3.2 respectively, we will obtain the exact thickness numbers of Kn x K2 and Km,n x K2.
Let G be a simple graph with n vertices, V(G) = jvi,..., vn} and V(K2) = {1,2}. Then G x K2 is a bipartite graph, the two vertex parts are {(vj, 1) | 1 < i < n} and {(vj, 2) | 1 < i < n}, so G x K2 is a subgraph of Kn,n which shows that 0(G x K2) < 0(Kn,„). Although the thickness of the complete bipartite Km,n have not been solved completely, when m = n, the following result is known.
Lemma 3.1 ([ ]). The thickness of the complete bipartite graph Kn,n is
*(*n,n) = [ ^
When n = 4p (p > 1), Chen and Yin [ ] gave a planar subgraphs decomposition of K4p,4p with p +1 planar subgraphs G1,..., Gp+1. Denote the two vertex parts of
K4p,4p by U = {u1,... , u4p} and V = {v1,..., v4p}, Figure 3 shows their planar subgraphs decomposition of K4p,4p, in which for each Gr (1 < r < p), both v4r-3 and v4r-1 join to each vertex in set Uf=1j=r{u4j_3, u4j-2}, both v4r-2 and v4r join to each vertex in set |JP=1 ¿=r{w4i-1,w4i}, both u4r-1 and u4r join to each vertex in set UP=1 i=r{v4j_3, v4j-1}, and both u4r_3 and u4r-2 join to each vertex in set UP=1 j=r {v4j-2, v4j}. Notice that Gp+1 is a perfect matching of K4p ,4p, the edge set of it is {wjVj | 1 < i < 4p}.
X. Guo and Y. Yang: The thickness of the Kronecker product of graphs
351
V4r- 3
U {u4i-3,U4i-2}
i= 1 ,i=r
U4r-1
U {v4i-3,v4i-1
= 1 ,i=r
U {v4i-2,v4i}
1 ,i=r
U4r 2
U {U4i-1,U4i}
= 1 ,i=r
(a) The graph Gr (1 < r < p). Utf U2J	fU4p-1T U4p
V1l V2l	|V4p-1
(b) The graph Gp+1.
V4p
Figure 3: A planar decomposition of K4p,4p.
Lemma 3.2 ([ ]). Suppose Kn,n is a complete bipartite graph with two vertex parts U = {«!,...,un} and V = {v^..., vn}. When n = 4p, there exists a planar subgraphs decomposition of K4p,4p with p +1 planar subgraphs Gi,..., Gp+1 in which Gp+1 is a perfect matching of K4p,4p with edge set {wjVj | 1 < i < 4p}.
Theorem 3.3. The thickness of the Kronecker product of Kn and K2 is
0(Kn X K2) =
Proof. Suppose that the vertex sets of Kn and K2 are {x1,..., xn } and {1,2} respectively. The graph Kn x K2 is a bipartite graph whose two vertex parts are {(xj, 1) | 1 < i < n}
and {(xj, 2) | 1 < i < n}, and edge set is {(xj, 1)(xj, 2) | 1 < i,j < n, i = j}. For 1 < i < n, 1 < k < 2, we denote the vertex (xj, k) of Kn x K2 by xk for simplicity.
Since |E(Kn x K2) have
n(n — 1) and |V(Kn x K2)| = 2n, from Theorem 2.2, we
0(Kn X K2) >
>	n( n	—1)1		"n"
	4n	— 4		4
(3.1)
In the following, we will construct planar decompositions of Kn x K2 with [n] subgraphs to complete the proof.
Case 1. When n = 4p.
Suppose that Kn n is a complete bipartite graph with vertex partition (X1, X2) in which
X1 = {a
, xn} and X2 = {x2,..., xn}. The graph Gp+1 is a perfect matching of
K4p,4p whose edge set is {x!x2 | 1 < i < n}, then Kn x K2 = Kn,n — Gp+1. From Lemma 3.2, there exists a planar decomposition {G1,..., Gp} of Kn x K2 in which Gr (1 < r < p) is isomorphic to the graph in Figure 3(a). Therefore, 0(K4p x K2) < p.
1
344
Ars Math. Contemp. 18 (2020) 339-357
Case 2. When n = 4p + 2.
When p > 1, we draw a graph G'p+1 as shown in Figure 4, then [G\,..., Gp, G'p+1} is a planar decomposition of K4p+2 x K2 withp +1 subgraphs, so we have 9(K4p+2 x K2) < p +1. When n = 2, K2 x K2 = 2K2 is a planar graph.
2
x4p+2
x4p+2
x4p+1
Figure 4: The graph G
p+1.
Case 3. When n = 4p +1 and n = 4p + 3.
Because K4p+1 x K2 is a subgraph of K4p+2 x K2, we have 6(K4p+1 x K2) < 9(K4p+2 x K2) = p +1. Similarly, when n = 4p + 3, we have 0(K4p+3 x K2) < 0(K4(p+1) x K2) = p +1.
Summarizing Cases 1, 2 and 3, we have
e(Kn x K2) < Theorem follows from inequalities (3.1) and (3.2).
Theorem 3.4. Let G be a simple graph on n (n > 2) vertices, then
(3.2) □
E(G) 2n — 2
< 6(G x K2) <
Proof. Because G x K2 is a subgraph of Kn x K2, we have 6(G x K2) < 6(Kn x K2). Combining it with Theorems 2.2 and 3.3, the theorem follows.	□
Lemma 3.5 ([ ]). The Kronecker product of Km,n and Kp,q is a disjoint union Kmp,nq U K.
Theorem 3.6. The thickness of the Kronecker product of Km,n and Kp,q is
e(Km
,n x Kp,q
) = max{0(Kmp,nq ),0(Kmq,np)}.
Proof. From Lemma 3.5, the proof is straightforward.	□
Because K2 is also K11, the following corollaries are easy to get, from Theorem 3.6 and Lemma 3.1.
Corollary 3.7. The thickness of the Kronecker product of Km,n and K2 is
e(Kmin x K2) = 0(Km,n). Corollary 3.8. The thickness of the Kronecker product of Kn,n and K2 is
' n + 2 ~
0(Kn,n x K2)
4
X. Guo and Y. Yang: The thickness of the Kronecker product of graphs
351
4 The thickness of the Kronecker product graph Kn,n,n x K2
Let (X, Y, Z) be the vertex partition of the complete tripartite graph m n (l < m < n) in which X = jxi,..., x}, Y = jyi,..., ym}, Z = jzi,..., zn}. Let {1, 2} be the vertex
set of K2. We denote the vertex (v, k) of K;jmi„ and k G {1,2}. For k = 1, 2, we denote Xk
x K by vf in which v G V(Kimi„) {xf, ...,xf}, Yk = {yf,...,ym} and
Zk = {zk,..., zn}. In Figure 5, we draw a sketch of the graph K;jmi„ x K2, in which the edge joining two vertex set indicates that each vertex in one vertex set is adjacent to each vertex in another vertex set. Suppose G(X1, Y2) is the graph induced by the vertex sets X1 and Y2 of Ki,m,n x K, then G(X1, Y2) is isomorphic to Kj,m, the graphs G(Y1, Z2), G(Z1 ,X2), G(X2,'y 1), G(Y2,Z1) and G(Z2,X1) are defined analogously. We define
and
then K
x K
G1 = G(X 1,Y2) U G(Y 1,Z2) U G(Z 1,X2)
G2 = G(X2,Y1) U G(Y2,Z1) U G(Z2,X1), G1 U G2.
Figure 5: The graph Kijmi„ x K2.
Theorem 4.1. The thickness of the Kronecker product graph K;jmi„ x K2 (1 < m < n) satisfies the inequality
1m + In + mn 2(1 + m + n) - 2
< 0(K,,m,n x K2) < 20(Km,n).
Proof. From Theorem 3.4, one can get the lower bound in this theorem easily. Any two graphs of G(X1, Y2), G(Y1, Z2) and G(Z1, X2) are disjoint with each other and l < m < n, so we have
^(G1) < max{0(G(X1, Y2), 0(G(Y1, Z2), 0(G(Z1, X2)} = 0(Km,n).
Similarly, we have
0(G2) < max{0(G(X2, Y1), 0(G(Y2, Z1), 0(G(Z2, X1))} = 0(Km,n).
Due to the graph Kijmj„ x K2 = G1 U G2, we have 0(Kijmj„ x K2) < 20(Km,n). Summarizing the above, the theorem is obtained.	□
In the following, we will construct planar decompositions of Kn n n x K2 when n = 4p, 4p +1,4p + 3 in Lemmas 4.2, 4.4 and 4.5 respectively. Then combining these lemmas with Theorem 2.2, we will get the thickness of K„ini„ x K2 and we will see when n = 4p+2, the upper and lower bound in Theorem 4.1 are equal, so both bounds in Theorem 4.1 are sharp.
156
Ars Math. Contemp. 18 (2020) 187-210
Lemma 4.2. When n = 4p, there exists a planar decomposition of the Kronecker product graph Kn,n,n x K2 with 2p +1 subgraphs.
Proof. Because |Xk| = |Yk| = |Zk| = n (k = 1,2), all the graphs G(X\Y2), G(Y\ Z2), G(Z\ X2), g(x2, Yx), G(Y2, Zx), G(Z2, Xx) are isomorphic to Kn,n.
Let {Gi,..., GpJ1} be the planar decomposition of Kn,n as shown in Figure 3. For 1 < r < p +1, Gr is a bipartite graph, so we also denote it by Gr (V, U). In Gr(V, U), we replace the vertex set V by X1, U by Y2, i.e., for each 1 < i < n, replace the vertex v by x1, and w by y2, then we get graph Gr(X1, Y2). Analogously, we obtain graphs Gr(Y1, Z2), Gr(Z1, X2), Gr(X2, Y1), Gr(Y2, Z1) and Gr(Z2, X1). For 1 < r < p + 1 , let
and
G1 = Gr(X1, Y2) U Gr(Y1, Z2) U Gr(Z1, X2)
G2 = Gr(X2,Y1) U Gr(Y2,Z1) U Gr(Z2,X1).
Because Gr (X1, Y2), Gr (Y1, Z2), Gr (Z1, X2) are all planar graphs and they are disjoint with each other, G^ is a planar graph. For the same reason, we have that G2 is also a planar graph.
Let graph Gp+1 be the graph Gp+1 U G^+1. We have
Gp+1 = Gp+1 U Gp+1
= {.UJ1(x1y2 U y1 z2 U z/x2)} U {¿KV U y^1 U z^x1)}
= A (xV^xVz2^1).
It is easy to see Gp+1 consists of n disjoint cycles of length 6, hence Gp+1 is a planar graph. Because
P+1
G(X 1,Y2) = U Gr(X1, Y2)
P+1
G(Y 1,Z2) = U Gr(Y 1,Z2),
G(Z 1,X2) = ^U1 Gr (Z 1,X2),
r=1
G(X 2,Y1) = ^LJ1 Gr (X 2,Y1),
r=1
and
P+1
G(Y2,Z1) = U Gr(Y2,Z1),
r=1
P+1
G(Z2,X1) = U Gr(Z2,X1),
r=1
we have
K„,„,„ x K2 = G1 U G2
= pjj1(g1 u g2)
r=1 p
= u (g1 u g2) u gp+1.
r=1
So we get a planar decomposition of K4pj4pj4p x K2 with 2p +1 subgraphs G1,..., G^, G2,...,G2, Gp+1. The proof is completed.	□
X. Guo and Y. Yang: The thickness of the Kronecker product of graphs	351
We draw the planar decomposition of K8,8,8 x K2 as shown in Figure 6.
Lemma 4.3 ([5]). Let G be a planar graph, and let f be a face in some planar embedding of G. Then G admits a planar embedding whose outer face has the same boundary as f.
(a) The graph G^.
(b) The graph G3,.
(c) The graph G|. Figure 6: A planar decomposition of K8,8,8 x K2.
158
Ars Math. Contemp. 18 (2020) 187-210
(d) The graph G?.
zi	xi
y4	yi
xj	z4
Z44	x44
y4	y44
x4	z4
z3	x43
y4	y3
x3	z34
z4	x4
y4	yl
x4	z4
z5	x5
y4	yi
x5	z.4
zi	x4 x6
	yi
x6	z4
zi	x7
y?	yi
4	z4
(e) The graph G3. Figure 6: A planar decomposition of K8,8,8 x K.
Lemma 4.4. When n = 4p + 1, there exists a planar decomposition of the Kronecker product graph Kn,n,n x K2 with 2p +1 subgraphs.
Proof. Case 1. When p < 1.
When p = 0, the Kronecker product graph Ki,i,i xK2 is a cycle of length 6, so Ki,i,i xK2 is a planar graph. When p = 1, as shown in Figure 7, we give a planar decomposition of
K5,5,5 x K2 with three subgraphs A, B and C.
Case 2. When p > 2.
G
J.; J ^p
Suppose that {G^..., Gp, G4,..., Gp, Gp+i} is the planar decomposition of K4p,4p,4p x
K2 as provided in the proof of Lemma 4.2. By adding vertices x4p+i, x4p+i, yip+i, y2p+i, z4p+i, z|p+i to each graph in this decomposition, and some modifications of adding and deleting edges to these graphs, a planar decomposition of K4p+i,4p+i,4p+i x K2 will be obtained.
For convenience, in Figure 3(a) we label some faces of Gr (1 < r < p) with face 1,2 and 3. As indicated in Figure 3(a), the face 1 is bounded by v4r-iM4r_3v4r_2M4r, the face 3 is its outer face, bounded by v4r_3w4r_2v4ru4r-i. The face 2 is bounded by u4r-3v4r-iM4r-2Vj in which vertex vj can be any vertex of UP=i i=r{v4i-2, v4i}. Because u4r_3 and u4r-2 in Gr (1 < r < p) is joined by 2p - 2 edge-disjoint paths of length two that we call parallel paths, we can change the order of these parallel paths without changing the planarity of Gr. Analogously, we can change the order of parallel paths between u4r_i and u4r, v4r_3 and v4r-i, v4r-2 and v4r. In addition, the subscripts of all the vertices are taken module 4p, except that of the new added vertices
x4p+i, x4p+i, y4p+i, y4p+i, z4p+i and z4p+i.
X. Guo and Y. Yang: The thickness of the Kronecker product of graphs
351
(a) The graph A.
(b) The graph B.
Figure 7: A planar decomposition of K5}5}5 x K2.
Step 1: Add the vertices xL+1 and y2p+1 to graph Gr (X1, Y2).
Place vertices x2p+1 and y2p+1 in face 1 and face 2 of Gr (X1, Y2), respectively. Join x;jp+1 to vertices y2r_3 and y2r. Change the order of the parallel paths between y2r_2 and y2r_3, such that x;jr+2 G UP=1 =r{xu-2,x\i} are incident with the face 2, andjoin y2p+1 to both x4r-1 and x;jr+2.
Step 2: Add the vertices x2p+1 and y|p+1 to graph Gr(X2, Y1).
Similar to step 1, place x2p+1 and y|p+1 in face 1 and face 2 of Gr(X2,Y"1), respectively. Join x2p+1 to both y\r_3 and y|r, join y|p+1 to both x2r-1 and x|r+2 G UP=1ji=r{x1i-2,
x4i}.
160
Ars Math. Contemp. 18 (2020) 187-210
Step 3: Add the vertices y|p+1 and z|p+1 to graph Gr (Y1, Z2).
Place yip+1 in face 3 of Gr (Y1, Z2) and join it to vertices z|r-2 and z|r-1. Place z|p+1 in face 1 of Gr (Y1, Z2) and join it to vertices y|r-2 and y4r-1.
Step 4: Add the vertices y|p+1 and z|p+1 to graph Gr(Y2, Z1).
Place y2p+1 in face 3 of Gr (Y2, Z1) and join it to vertices z|r_2 and z4r-1. Place z|p+1 in face 1 of Gr (Y2, Z1) and join it to vertices y|r_2 and y|r-1.
Step 5: Add the vertices z4p+1 and x2p+1 to graph Gr(Z1, X2).
Place z|p+1 in face 1 of Gr (Z1, X2) and join it to vertices x2r_3 and x2r. Place x4p+1 in face 3 of Gr (Z1, X2) and join it to vertices z[r_3 and z4r.
Step 6: Add the vertices z2p+1 and x4p+1 to graph Gr (Z2, X1).
Place z2p+1 in face 1 of Gr (Z2, X1) and join it to vertices x4r_3 and x4r. Place x4p+1 in face 3 of Gr (Z2, X1) and join it to vertices z4r_3 and z4r.
We denote the above graphs we obtain from Steps 1-6 by Gr(X1, Y2), Gr(X2, Y1), Gr(Y1, Z2), Gr(Y2, Z1), Gr(Z1, X2) and Gr(Z2, X1) respectively. Let
G1 = Gr(X1, Y2) U Gr(Y1, Z2) U Gr(Z1, X2)
and
G2 = Gr (x2,y 1) u Gr (y2,z 1) u Gr(z2 ,x 1).
Step 7: Add the edges z4rx4r, yir— 1,z4r_2y4r—2,x4r—3 and z4rx^,
-3z4r-3 to graphs G4 and G2 respectively, 1 < r < p.
For graph Gr (Y1, Z2) c G?1, we delete the edge y4r-3z4r and join the vertex y4r-1 to vertex z4r-4, then we get a planar graph Gr (Y1, Z2). According to Lemma 4.3, the graph Gr (YZ2) has a planar embedding whose outer face has the same boundary as face 2, then the vertex z2r_3 is on the boundary of this outer face.
For graph Gr (ZX2) c G?4, delete the edge z4r_2x|r-1 and join z4r to x4r, then we get a planar graph Gr (ZX2). According to Lemma4.3, the graph Gr (Z1, X2) has aplanar embedding whose outer face has boundary as z4rx2rz4r_2x2z4r (x2 G UP=1 i=r{x2i—1, x^J), then the vertex z4r_2 is on the boundary of this outer face.
Since the vertices x4r-3 and y4r-2 are on the boundary of the outer face of the embedding of Gr (XY2) c G^, we can join x4r-3 to z4r-3, y2r-2 to z4r-2 without edge crossing. Then we get a planar graph G^.
With the same process, for the graph G^, we delete edges y4r-3z4r and z4r_2x4r-1, join y4r-1 to z4r-1, join z4r to x4r, join x|r_3 to z|r_3 and join y4r-2 to z|r_2, then we get a planar graph G^.
Table 1 shows the edges that we add to G^ and Gj; (1 < r < p) in Steps 1-7. Step 8: The remaining edges form a planar graph Gp+1.
The edges that belong to K4p+14p+14p+1 x K2 but not to any G^, Gj; (1 < r < p) are shown in Table 2, in which the edges in the test two rows list the edges deleted in Step 7. The remaining edges form a graph, denote by Gp+1. We draw a planar embedding of Gp+1 in Figure 8, so Gp+1 is a planar graph.
X. Guo and Y. Yang: The thickness of the Kronecker product of graphs	351
Table 1: The edges we add to G1 and G^ (1 < r < p).
Edges				Subscript
1 2 x4p+1yi 1 2 x4p+1zi	21 x4p+1yi , 21 x4p+1zi ,	12 z4p+1xi 12	2 1 z4p+1xi , 21	i = 4r — 3, 4r.
1 2 y4p+1zi 12 y4p+1xi	21 y4p+1zi , 21 y4p+1xi ,	12 z4p+1yi y^2	2 1 z4p+1yi , yfz1,	i = 4r — 2, 4r — 1.
Table 2: The edges of Gp+1.
Edges	Subscript (1 < r < p)
1 22 1 1 22 1 x4p+1 yi , x4p+1 yi , z4p+1 , z4p+1 , 1 22 1 1221 x4p+1zi , x4p+1zi , , ,	i = 4r — 2, 4r — 1.
1 22 1 1 22 1 y4p+1zi , y4p+1zi , z4p+1yi , z4p+1yi , 1 22 1 1221 y4p+1 , y4p+1xi , yi , yi ,	i = 4r — 3, 4r.
12 2 1	i = 4r — 3, 4r — 2, 4r — 1, 4r.
12 21 12 21 12 21 sy* Q 1 sy*^ ry* si 1 Ql? ? 'T*	i = 4p + 1.
12 2 1 y^ y2 j	i = 4r — 3, j = 4r.
12 2 1 x j, x j,	i = 4r — 2, j = 4r — 1.
Therefore [G\,..., Gp, G2,..., Gp, Gp+1} is a planar decomposition of
K4p+1,4p+1,4p+1 x K2, the Lemma follows.	□
Figure 9 illustrates a planar decomposition of K9,9,9 x K2 with five subgraphs. A graph G is said to be thickness t-minimal, if 0(G) = t and every proper subgraphs of it have a thickness less than t.
Lemma 4.5. When n = 4p + 3, there exists a planar decomposition of Kronecker product graph K4p+3,4p+3,4p+3 x K2 with 2p + 2 subgraphs.
Proof. Case 1. When p = 0.
As shown in Figure 10, we give a planar decomposition of K3,3,3 x K2 with 2 subgraphs. Case 2. When p > 1.
The graph K4p+3,4p+3 is a thickness (p + 2)-minimal graph. Hobbs, Grossman [ ] and Bouwer, Broere [6] proved it independently, by giving two different planar subgraphs decompositions {H1,..., Hp+2} of K4p+3,4p+3 in which ffp+2 contains only one edge. Suppose that the two vertex parts of Kn,n is {v1,..., vn} and {u1,..., un}, the only one edge in the Hp+2 is vawb (the edge is v1 u1 in [11] and v4p+3u4p-1 in [ ]). For 1 < i < p + 2, Hj is a bipartite graph, so we also denote it by Hj(V, U).
Because Kn,n,n xK2 = G1 UG2 in which G1 = G(X 1,Y2)UG(Y 1,Z2)UG(Z 1,X2) and G2 = G(X2,V1) U G(Y2,Z1) U G(Z2,X1), |Xj| = |Yj| = |Zj| = n (i = 1, 2), all the graphs G(X 1,Y2),G(Y 1,Z2),G(Z 1,X2),G(X2,Y 1),G(Y2,Z1) and G(Z2,X1) are isomorphic to Kn,n.
354
Ars Math. Contemp. 18 (2020) 339-357
x4p+1
Figure 8: The graph Gp+1.
(a) The graph G jj.
Figure 10: A planar decomposition of K3 3 3 x K2.
X. Guo and Y Yang: The thickness of the Kronecker product of graphs	353
(d) The graph G|.
Figure 9: A planar decomposition of x K2.
354
Ars Math. Contemp. 18 (2020) 339-357
Figure 9: A planar decomposition of Kq,q,q x K2.
2
X
X
Figure 10: A planar decomposition of K3 3 3 x K2.
X. Guo and Y. Yang: The thickness of the Kronecker product of graphs
351
For graph Hj(V, U) (1 < i < p + 2), we replace the vertex set V by X1, U by Y2, i.e., for each 1 < t < n, replace the vertex vt by x^, and ut by yt2, then we get a graph Hi(x 1,Y2). Analogously, we can obtain graphs Hi(Y 1,Z2),Hi(Z 1,X2),Hi(X2,Y1), Hi(Y2,Z1) and H^Z2,X1). For 1 < i < p + 2, let
Hi = Hi(X 1,Y2) U Hi(Y 1,Z2) U Hi(Z 1,X2),
then Hi is a planar graph, because Hi (X1, Y2), Hi (Y1, Z2), Hi (Z1, X2) are disjoint with each other. For the same reason, the graph
H2 = Hi(X2,Y1) U Hi(Y2,Z1) U Hi(Z2,X1)
is also a planar graph, 1 < i < p + 2. And we have
K4p+3,4p+3,4p+3 X K2 = G1 U G2 = ^(H/ U H2),
in
i=1
in which E(Hp+2) = {xa^^^x^ and E(Hp+2) = {xay61,y2z61 ,z2x1}.
In the following, we will add edges in E(H^+2) to graphs H2 and H2, add edges i E(Hp+2) to graphs H and H to complete the proof. From Lemma 4.3, there exists a planar embedding of H1(Y1, Z2) such that vertex on the boundary of its outer face, exists a planar embedding of H1(X1, Y2) such that x^ on the boundary of its outer face. Then we join z^ to x^ without edge crossing. Suppose y1 is on the boundary of inner face F of the embedding of H1(Y1, Z2), put the embedding of H1(Z 1,X2) in face F with xa on the boundary of its outer face, then we join xa to y^ without edge crossing. After adding both xay1 and z^x^ to H without edge crossing, we get a planar graph H1. With the same process, we add both xay2 and z^ to H2 without edge crossing, then we get a planar graph Hi2. From Lemma4.3, we can also add y^z^ to H2, and y^z^ to H2 without edge crossing, then we get planar graphs H2 and H| respectively.
Then we get a planar decomposition
Hl,Hl,H3,
ttI	TT2
>Hp+1,H1 ,H2 ,H3 ,
2
> Hp+1 |
of K4p+3,4p+3,4p+3 x K with 2p + 2 subgraphs. Summarizing Cases 1 and 2, the lemma follows.
Theorem 4.6. The thickness of the Kronecker product of Kn,n,n and K2 is
' n + 1"
□
x K2)
2
Proof. Because of E(Kn,n,n x K2) = 6n2 and V(Kn,n,n x K2) = 6n, from Theorem 2.2, we have
6n2
0(KW x K2) >
2(6n) - 4
nn 2 + 6n — 2
n + 1 2
(4.1)
When n = 4p + 2, because ^4^+2,4^+2,4^+2 x K2 is a subgraph of ^+3,4^+3,4^+3 x K2, we have ^(^4^+2,4^+2,4^+2 x K2) < #(^+3,4^+3,4^+3 x K2). Combining this fact with Lemmas 4.2, 4.4 and 4.5, we have
0(K„,„,„ x K2) <
n + 1 2
From inequalities (4.1) and (4.2), the theorem is obtained.
(4.2)
□
166
Ars Math. Contemp. 18 (2020) 187-210
ORCID iDs
Xia Guo © https://orcid.org/0000-0003-0217-105X Yan Yang © https://orcid.org/0000-0002-9666-5167
References
[1]	V. B. Alekseev and V. S. Goncakov, The thickness of an arbitrary complete graph, Mat. Sb. (N.S.) 101(143) (1976), 212-230, doi:10.1070/sm1976v030n02abeh002267.
[2]	L. Beaudou, P. Dorbec, S. Gravier and P. K. Jha, On planarity of direct product of multipartite complete graphs, Discrete Math. Algorithms Appl. 1 (2009), 85-104, doi:10.1142/ s179383090900004x.
[3]	L. W. Beineke and F. Harary, The thickness of the complete graph, Canadian J. Math. 17 (1965), 850-859, doi:10.4153/cjm-1965-084-2.
[4]	L. W. Beineke, F. Harary and J. W. Moon, On the thickness of the complete bipartite graph, Proc. Cambridge Philos. Soc. 60 (1964), 1-5, doi:10.1017/s0305004100037385.
[5]	J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer, New York, 2008, doi:10.1007/978-1-84628-970-5.
[6]	I. Z. Bouwer and I. Broere, Note on t-minimal complete bipartite graphs, Canad. Math. Bull. 11 (1968), 729-732, doi:10.4153/cmb-1968-088-x.
[7]	Y. Chen and Y. Yang, The thickness of the complete multipartite graphs and the join of graphs, J. Comb. Optim. 34 (2017), 194-202, doi:10.1007/s10878-016-0057-1.
[8]	Y. Chen and X. Yin, The thickness of the Cartesian product of two graphs, Canad. Math. Bull. 59 (2016), 705-720, doi:10.4153/cmb-2016-020-1.
[9]	D. Duffus, B. Sands and R. E. Woodrow, On the chromatic number of the product of graphs, J. Graph Theory 9 (1985), 487-495, doi:10.1002/jgt.3190090409.
[10]	M. Farzan and D. A. Waller, Kronecker products and local joins of graphs, Canadian J. Math. 29 (1977), 255-269, doi:10.4153/cjm-1977-027-1.
[11]	A. M. Hobbs and J. W. Grossman, A class of thickness-minimal graphs, J. Res. Nat. Bur. Standards Sect. B 72B (1968), 145-153, https://nvlpubs.nist.gov/nistpubs/ jres/72B/jresv72Bn2p145_A1b.pdf.
[12]	S. KlavZar, Coloring graph products—a survey, Discrete Math. 155 (1996), 135-145, doi:10. 1016/0012-365x(94)00377-u.
[13]	M. Kleinert, Die Dicke des n-dimensionalen Wiirfel-Graphen, J. Comb. Theory 3 (1967), 1015, doi:10.1016/s0021-9800(67)80010-3.
[14]	J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos and Z. Ghahramani, Kronecker graphs: an approach to modeling networks, J. Mach. Learn. Res. 11 (2010), 985-1042, https:// www.jmlr.org/papers/v11/leskovec10a.html.
[15]	P. Mutzel, T. Odenthal and M. Scharbrodt, The thickness of graphs: a survey, Graphs Combin. 14 (1998), 59-73, doi:10.1007/pl00007219.
[16]	W. T. Tutte, The thickness of a graph, Indag. Math. 66 (1963), 567-577, doi:10.1016/ s1385-7258(63)50055-9.
[17]	J. M. Vasak, The Thickness of the Complete Graph, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1976, https://www.proquest.com/docview/302 82 0 0 90.
[18]	W. Wang and Z. Yan, Connectivity of Kronecker products with complete multipartite graphs, Discrete Appl. Math. 161 (2013), 1655-1659, doi:10.1016/j.dam.2013.01.009.
X. Guo and Y. Yang: The thickness of the Kronecker product of graphs	351
[19]	Y. Yang, Remarks on the thickness of Kn>n,n, Ars Math. Contemp. 12 (2017), 135-144, doi: 10.26493/1855-3974.823.068.
[20]	Y. Yang and Y. Chen, The thickness of amalgamations and Cartesian product of graphs, Discuss. Math. Graph Theory 37 (2017), 561-572, doi:10.7151/dmgt.1942.