Electronic Journal of Graph Theory and Applications 12 .
, 117Ae123 The dispersability of the Kronecker cover of the product of complete graphs and cycles Zeling Shao.
Yaqin Cui.
Zhiguo Li* Department of Mathematics.
Hebei University of Technology.
China zelingshao@163.
com, c260613507@163.
Zhiguolee@hebut.
*corresponding author Abstract The Kronecker cover of a graph G is the Kronecker product of G and K2 .
The matching book embedding of a graph G is an embedding of G with the vertices on the spine, each edge within a single page so that the edges on each page do not intersect and the degree of vertices on each page is at most one.
The matching book thickness of G is the minimum number of pages in a matching book embeding of G and it denoted by mbt(G).
A graph G is dispersable if mbt(G) = OI(G), nearly dispersable if mbt(G) = OI(G) 1.
In this paper, the dispersability of the Kronecker cover of the Cartesian product of complete graphs Kp and cycles Cq is determined.
Keywords: matching book embedding, matching book thickness.
Kronecker cover, complete graph, cycle Mathematics Subject Classification : 05C10 DOI: 10.
5614/ejgta.
Introduction The book embedding of a graph was first introduced by Bernhart and Kainen .
They defined an n-book which is composed of a line L in 3-space.
alled spine ) and n distinct half-planes.
alled page.
, where L forms the common boundary of the n half-planes.
An n-book embedding is an embedding of G such that each vertex of a graph G is placed on the spine and each edge is placed on at most one page with no two edges on the same page intersecting.
The book thickness of a graph G is the smallest n so that G has an n-book embedding and it denoted by bt(G).
Received: 30 November 2023.
Revised: 7 March 2024.
Accepted: 16 March 2024.
The dispersability of the Kronecker cover of the product of complete graphs and cycles Shao et al.
A matching book embedding of a graph G is a book embedding where on each page the maximum degree of vertices is at most one.
The matching book thickness of a graph G is the smallest k such that G has an k page matching book embedding and it denoted by mbt(G).
A graph G is dispersable .
nearly dispersabl.
if mbt(G) = OI(G) .
if mbt(G) = OI(G) .
, where OI(G) represents the maximum number of edges adjacent to a vertex v in the graph G.
In 1998.
Overbay proved the complete bipartite graph Kn,n .
Ou .
, even cycle C2n .
Ou .
, binary n-cube Q.
Ou .
and tree are dispersable .
, also she got that the odd cycles and complete graphs Kn .
Ou .
are near-dispersable.
Kainen obtained that the the Cartesian product of two even cycles is dipersable, the product of an odd cycle and an even cycle is nearly dispersable .
Shao-et-al proved that for all odd integers s, t and s Ou t Ou 7, mbt(Cs 2Ct ) = 5 .
This solved the matching book embedding of the Cartesian product of two cycles.
Shao-et-al also obtained that Kp 2Cq is nearly dispersable when p, q Ou 3 .
The main goal of this paper is to prove that the matching book thickness of the Kronecker cover of the Cartesian product of complete graphs Kp and cycles Cq is equal to p 1 when p, q Ou 3.
Preliminaries In this section, we present some definitions and results which we needed in our work.
Definition 1.
The matching book embedding of G is an embedding of a graph G with the vertices on the spine, each edge within a single page so that the edges on each page do not intersect and the degree of vertices on each page is at most one.
Definition 2.
The matching book thickness of a graph G is the minimum number of pages in a matching book embeding of G and it denoted by mbt(G).
Definition 3.
The Cartesian product of two arbitrary graphs G and B is the graph denoted by G2B whose vertex set is V (G) y V (B), the vertex .
1 , v1 ) and the vertex .
2 , v2 ) are adjacent in G2B if and only if u1 = u2 and v1 is adjacent to v2 in B, or v1 = v2 and u1 is adjacent to u2 in G.
Definition 4.
The product G1 O G2 of two graphs G1 and G2 .
ften known as their Kronecker produc.
has vertex set V (G1 O G2 ) equal to the Cartesian product V (G1 ) y V (G2 ) of the vertex sets of the given graphs, with adjacency in G1 O G2 given by .
1 , w1 ) O .
2 , w2 ) if and only if v1 O v2 in G1 and w1 O w2 in G2 .
The Kronecker cover, also known as the canonical double cover, of a graph G is essentially the Kronecker product of G and the complete graph K2 , where the projection morphism p : G O K2 Ie G on vertices is defined by .
, .
7Ie v, .
, .
and this induces a .
map on edges :
, .
, .
, .
] 7Ie .
, .
, .
, .
, .
] The dispersability of the Kronecker cover of the product of complete graphs and cycles Shao et al.
Let D denote the Kronecker cover of graph G.
In graph D, both the number of vertices and the number of edges are twice that of graph G.
Lemma 2.
If p : D Ie G is a double cover projection, then the vertex v has degree d in G if and only if the two associated vertices v1 and v2 in D both have degree d.
Lemma 2.
For any simple graph G.
OI(G) O NA (G) O mbt(G), where NA (G) is the chromatic index of G.
Lemma 2.
For a regular graph G.
G is dispersable only if G is bipartite.
The dispersability of D(Kp 2Cq ) In this section, we study the matching book embedding and dispersability of some standard graphs and their Cartesian product.
Lemma 3.
The Kronecker cover D of cycle Cn is dispersable.
Proof.
According to Definition 4, it is easy to see that the Kronecker cover of a cycle Cn is an even cycle C2n regardless of whether n is odd or even.
Therefore, the Kronecker cover of a cycle is dispersable.
Lemma 3.
The Kronecker cover D of complete graph Kn is dispersable.
Proof.
Let V (Kn ) = .
, 2, .
, .
Assuming that in the Kronecker cover of the complete graph, both i1 and i2 correspond to the vertex i in the complete graph, where 1 O i O n.
It is clear that mbt(D) Ou OI(D) = n Oe 1 by Lemma 2.
According to the parity of n, we need to consider two cases to compute the matching book thickness of D.
Case 1.
n is odd For the Kronecker cover of the complete graph, we assign the vertex ordering as 11 , 22 , 31 , 42 , , .
Oe .
1 , .
Oe .
2 , n1 , n2 , .
Oe .
1 , .
Oe .
2 , .
Oe .
1 , .
Oe .
2 , .
, 21 , 12 .
The matching book embedding of D in this case is given as follows:
Page 1: edges {.
1 , j2 ).
Oe j = 2.
3 O i O n, i is od.
, edges {.
2 , j1 ).
Oe j = 2.
4 O i O n Oe 1, i is eve.
, and edges {.
, 22 ), .
2 , .
Oe .
1 )}.
Page 2: edges {.
1 , j2 ).
Oe i = 2.
3 O j O n, j is od.
, edges {.
2 , j1 ).
Oe i = 2.
4 O j O n Oe 1, j is eve.
, and edges {.
, 12 ), (.
Oe .
2 , n1 )}.
Page 3: edges {.
1 , j2 ).
Oe j = 4.
5 O i O n, i is od.
, edges {.
2 , j1 ).
Oe j = 4.
6 O i O n Oe 1, i is eve.
, and edges {.
, 42 ), .
, 31 ), (.
Oe .
1 , .
Oe .
2 ), .
2 , .
Oe .
1 )}.
Page 4: edges {.
1 , j2 ).
Oe i = 4.
5 O j O n, i is od.
, edges {.
2 , j1 ).
Oe i = 4.
6 O j O n Oe 1, i is eve.
, and edges {.
, 12 ), .
, 21 ), (.
Oe .
1 , .
Oe .
2 ), (.
Oe .
2 , n1 )}.
a ) , ( n 1 ) ).
= 1 and t = 2 Page nOe2: edges {.
, .
Oe.
2 ), .
, .
Oe.
1 ), .
, .
Oe.
2 ), .
, (( nOe1 nOe1 when 2 is od.
, and edges {.
1 , 12 ), .
2 , 21 ), (.
Oe.
1 , 32 ), (.
Oe.
2 , 41 ), .
, (( n 3 ) , ( n 1 .
= 1 and t = 2 when 2 is eve.
The dispersability of the Kronecker cover of the product of complete graphs and cycles Shao et al.
Page nOe1: edges {(.
Oe.
1 , 12 ), (.
Oe.
2 , 21 ), (.
Oe.
1 , 32 ), .
, (( n 1 ) , ( nOe1 ) ).
= 1 and t = 2 when 2 is eve.
, and edges {.
, n2 ), .
, n1 ), .
, .
Oe.
2 ), .
, .
Oe.
1 ) .
, (( n 1 ) , ( n 3 .
= 1 and t = 2 when 2 is od.
It is clear that mbt(D) O n Oe 1.
Therefore, the Kronecker cover of complete graph is dispersable when n is odd.
ee Fig.
1 for the case n = .
Fig.
1 The matching book embedding of D(K5 ) Case 2.
n is even Let the vertex ordering on spine be as 11 , 22 , 31 , 42 , .
, .
Oe.
1 , n2 , n1 , .
Oe.
2 , .
Oe.
1 , .
Oe .
2 , .
, 21 , 12 .
The matching book embedding of D in this case is given as follows:
Page 1: edges {.
1 , j2 ).
Oe j = 2.
3 O i O n Oe 1, i is od.
, edges {.
2 , j1 ).
Oe j = 2.
4 O i O n, i is eve.
, and edges {.
, 22 ), .
1 , .
Oe .
2 )}.
Page 2: edges {.
1 , j2 ).
Oe i = 2.
3 O j O n Oe 1, j is od.
, edges {.
2 , j1 ).
Oe i = 2.
4 O j O n, j is eve.
, and edges {.
, 12 ), (.
Oe .
1 , n2 )}.
Page 3: edges {.
1 , j2 ).
Oe j = 4.
5 O i O n Oe 1, i is od.
, edges {.
2 , j1 ).
Oe j = 4.
6 O i O n, i is eve.
, and edges {.
, 42 ), .
, 31 ), (.
Oe .
2 , .
Oe .
1 ), .
1 , .
Oe .
2 )}.
Page 4: edges {.
1 , j2 ).
Oe i = 4.
5 O j O n Oe 1, i is od.
, edges {.
2 , j1 ).
Oe i = 4.
6 O j O n, i is eve.
, and edges {.
, 12 ), .
, 21 ), (.
Oe .
2 , .
Oe .
1 ), (.
Oe .
1 , n2 )}.
a ) , ( n ) ).
= 1 and t = 2 Page nOe3: edges {.
, .
Oe.
2 ), .
, .
Oe.
1 ), .
, .
Oe.
2 ), .
, (( nOe2 2 s 2 t when n2 is eve.
, and edges {(.
Oe.
1 , 12 ), .
2 , 21 ), .
1 , 32 ), (.
Oe.
2 , 41 ), (.
Oe.
1 , 52 ), .
, (( n 4 ( 2 )t ).
= 1 and t = 2 when 2 is eve.
) ).
= 1 and t = 2 Page nOe2: edges {(.
Oe.
1 , 12 ), (.
Oe.
2 , 21 ), (.
Oe.
1 , 32 ), .
, (( n2 )s , ( nOe2 when 2 is eve.
, and edges {.
, .
Oe.
2 ), .
, n1 ), .
, n2 ), .
, .
Oe.
1 ), .
, .
Oe.
2 ), .
, (( n 2 ( n 4 ).
Page nOe1: edges {.
1 , 12 ), (.
Oe.
2 , 21 ), .
, (( n 2 ) , ( n ) ).
= 2 and t = 1 when n2 is eve.
, 2 s 2 t and edges {.
, n2 ), .
, .
Oe .
1 ), .
, (( 2 )s , ( 2 )t ).
= 1 and t = 2 when n2 is od.
Thus, mbt(D) O n Oe 1, the Kronecker cover of complete graph is dispersable when n is even.
ee Fig.
2 for the case n = .
Therefore, the result is established.
Lemma 3.
Let G be an arbitrary graph and H be a graph such that its Kronecker cover D(H) is a dispersible bipartite graph, then mbt(D(G2H)) O mbt(D(G)) OI(D(H)).
Proof.
Since D(H) is dispersable, there is a OI(D(H))-edge coloring of D(H) and a corresponding matching book embedding of D(H) in a OI(D(H))-page book so that all edges of one color The dispersability of the Kronecker cover of the product of complete graphs and cycles Shao et al.
Fig.
2 The matching book embedding of D(K4 ) lie on the same page.
Since D(H) is bipartite, there is also a 2-coloring of the vertices of D(H) using colors a and b.
Let |V (G)| = p, |V (H)| = q.
There are pq vertices for graph G2H, and these vertices can be separated into p rows and q columns.
Let the vertex set be .
O i O p, 1 O j O .
, where j represents the column number, and i is a consecutive number from top to bottom in each column, with odd columns and even columns in opposite order.
Now we consider the matching book embedding of D(G2H).
Assuming that both u1 and u2 in D(G2H) correspond to the vertex u in G2H.
V (D(G2H)) = .
O i O p, 1 O j O q, k = 1, .
Dividing the vertices set of D(G2H) into j groups, where each group consists of vertices that share the same j value.
Since D(H) has an even number of vertices, it is possible to place the vertices of each group symmetrically on the left and right sides of the circle, such that j on one side increases from top to bottom, while k alternates between 1 and 2 along the circle.
Take a matching book embedding of D(G) in mbt(D(G)) pages.
Using a matching book embedding of D(G), replace each group with a copy of this matching book embedding of D(G).
Since each of these copies are placed on the circle, the edges of D(G2H) corresponding to 2.
E(G)| edges of D(G) can all be matching book embedded in mbt(D(G)) pages.
The remaining 2.
E(H)| edges of D(G2H) connect corresponding vertices in adjacent copies of D(G).
Since D(H) is bipartite, edges of D(H) connect vertices of different colors.
Since the order of vertices in adjacent copies of D(G) is same on i, edges connect two adjacent copies corresponding to a single edge of D(H) can be embedded in the appropriate page as concentric semicircles, which makes sure that the book embedding is matching.
Since mbt(D(H)) = OI(D(H)), the edges of D(H) can also be matching book embedded in OI(D(H)) pages.
Hence all edges of D(G2H) can be matching book embedded in mbt(D(G)) OI(D(H)) pages.
ee Fig.
3 for the case G = K3 .
H = C4 ).
Theorem 3.
For p, q Ou 3, mbt(D(Kp 2Cq )) = OI(D(Kp 2Cq )) = p 1.
Proof.
Since OI(D(Kp 2Cq )) = p 1, mbt(D(Kp 2Cq )) Ou p 1 by Lemma 2.
It is known from Lemma 3.
1 that the Kronecker cover of cycle is dispersable.
According to Lemma 3.
3, it is easy to see that mbt(D(Kp 2Cq )) O mbt(D(Kp )) OI(D(Cq )) = mbt(D(Kp )) 2.
Thus, by Lemma 3.
we have mbt(D(Kp 2Cq )) O p Oe 1 2 = p 1.
Therefore, mbt(D(Kp 2Cq )) = OI(D(Kp 2Cq )), hence D(Kp 2Cq ) is dispersable when p, q Ou 3.
The dispersability of the Kronecker cover of the product of complete graphs and cycles Shao et al.
Fig.
3 The matching book embedding of D(K3 2C4 ) Conclusions In this paper, we studied the dispersability of some standard graphs and obtain that the Kronecker cover of the Cartesian product of complete graphs Kp and cycles Cq is dispersable when p, q Ou 3.
By the results of Kainen and Overbay, the odd cycles and the complete graphs Kn .
Ou .
are all near-dispersability.
It is interesting to find that the matching book thickness become smaller after the Kronecker cover operation as to complete graphs and cycles in this work.
Naturally, we raise a question as follows.
Question: Is the matching book thickness nonincreasing after Kronecker cover as to general Acknowledgement This work was partially funded by Science and Technology Project of Hebei Education Department.
China (No.
ZD2020.
and the Natural Science Foundation of Hebei Province.
China (No.
A2021202.
References