Zeling Shao, Yaqin Cui, Zhiguo Li*

Department of Mathematics, Hebei University of Technology, China

zelingshao@163.com, c260613507@163.com, Zhiguolee@hebut.edu.cn

*corresponding author

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 embeddding of G and it denoted by mbt(G). A graph G is dispersable if mbt(G) = ∆(G), nearly dispersable if mbt(G) = ∆(G) + 1. In this paper, the dispersability of the Kronecker cover of the Cartesian product of complete graphs K^p and cycles C^q is determined.

Keywords: matching book embedding, matching book thickness, Kronecker cover, complete graph, cycle

Mathematics Subject Classification : 05C10

DOI: 10.5614/ejgta.2024.12.1.10

1. Introduction

The book embedding of a graph was first introduced by Bernhart and Kainen [1]. They defined an n-book which is composed of a line L in 3-space(called spine ) and n distinct half-planes(called pages), 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.

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 (resp. nearly dispersable) if mbt(G) = ∆(G) (resp. if mbt(G) = ∆(G) + 1), where ∆(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 (n ≥ 1), even cycle C2ⁿ (n ≥ 2), binary n-cube Q(n) (n ≥ 0) and tree are dispersable [5], also she got that the odd cycles and complete graphs Kn(n ≥ 3) 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 [4]. Shao-et-al proved that for all odd integers s, t and s ≥ t ≥ 7, mbt(Cs✷Ct) = 5 [8]. This solved the matching book embedding of the Cartesian product of two cycles. Shao-et-al also obtained that Kp✷C^q is nearly dispersable when p, q ≥ 3 [7].

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 K^p and cycles C^q is equal to p + 1 when p, q ≥ 3.

2. 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 embeddding of G and it denoted by mbt(G).

Definition 3. [2] The Cartesian product of two arbitrary graphs G and B is the graph denoted by G✷B whose vertex set is V (G) × V (B), the vertex (u1, v1) and the vertex (u2, v2) are adjacent in G✷B if and only if u¹ = u² and v¹ is adjacent to v² in B, or v¹ = v² and u¹ is adjacent to u² in G.

Definition 4. [9] The product G¹ ∧ G² of two graphs G¹ and G² (often known as their Kronecker product) has vertex set V (G¹ ∧ G2) equal to the Cartesian product V (G1) × V (G2) of the vertex sets of the given graphs, with adjacency in G¹ ∧ G² given by (v1, w1) ∼ (v2, w2) if and only if v¹ ∼ v² in G¹ and w¹ ∼ w² 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 ∧ K² → G on vertices is defined by

(v, 0) (v, 1) 7→ v,

and this induces a (2:1) map on edges :

\[[(v,0),(w,1)] [(v,1),(w,0)]\] \(\mapsto\) \((v,w).\)

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.1. [9] If \(p: D \to G\) is a double cover projection, then the vertex v has degree d in G if and only if the two associated vertices \(v_1\) and \(v_2\) in D both have degree d.

Lemma 2.2. [5] For any simple graph G, \(\Delta(G) \leq \chi'(G) \leq mbt(G)\), where \(\chi'(G)\) is the chromatic index of G.

Lemma 2.3. [5] For a regular graph G, G is dispersable only if G is bipartite.

3. The dispersability of \(D(K_p \square C_q)\)

In this section, we study the matching book embedding and dispersability of some standard graphs and their Cartesian product.

Lemma 3.1. The Kronecker cover D of cycle \(C_n\) is dispersable.

Proof. According to Definition 4, it is easy to see that the Kronecker cover of a cycle \(C_n\) is an even cycle \(C_{2n}\) regardless of whether n is odd or even. Therefore, the Kronecker cover of a cycle is dispersable.

Lemma 3.2. The Kronecker cover D of complete graph \(K_n\) is dispersable.

Proof. Let \(V(K_n) = \{1, 2, ..., n\}\). Assuming that in the Kronecker cover of the complete graph, both \(i_1\) and \(i_2\) correspond to the vertex i in the complete graph, where \(1 \le i \le n\). It is clear that \(mbt(D) \ge \Delta(D) = n - 1\) by Lemma 2.1. 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 \(1_1, 2_2, 3_1, 4_2, \ldots, (n-2)_1, (n-1)_2, n_1, n_2, (n-1)_1, (n-2)_2, (n-3)_1, (n-4)_2, \ldots, 2_1, 1_2\). The matching book embedding of D in this case is given as follows:

Page 1: edges \(\{(i_1,j_2)|i-j=2; 3\leq i\leq n, i \text{ is odd}\}\), edges \(\{(i_2,j_1)|i-j=2; 4\leq i\leq n-1, i \text{ is even}\}\), and edges \(\{(1_1,2_2), (n_2,(n-1)_1)\}\).

Page 2: edges \(\{(i_1, j_2)|j-i=2; 3 \le j \le n, j \text{ is odd}\}\), edges \(\{(i_2, j_1)|j-i=2; 4 \le j \le n-1, j \text{ is even}\}\), and edges \(\{(2_1, 1_2), ((n-1)_2, n_1)\}\).

Page 3: edges \(\{(i_1, j_2)|i-j=4; 5 \le i \le n, i \text{ is odd}\}\), edges \(\{(i_2, j_1)|i-j=4; 6 \le i \le n-1, i \text{ is even}\}\), and edges \(\{(1_1, 4_2), (2_2, 3_1), ((n-1)_1, (n-2)_2), (n_2, (n-3)_1)\}\).

Page 4: edges \(\{(i_1, j_2)|j-i=4; 5 \leq j \leq n, i \text{ is odd}\}\), edges \(\{(i_2, j_1)|j-i=4; 6 \leq j \leq n-1, i \text{ is even}\}\), and edges \(\{(4_1, 1_2), (3_2, 2_1), ((n-2)_1, (n-1)_2), ((n-3)_2, n_1)\}\).

Page n-2: edges \(\{(1_1,(n-1)_2),(2_2,(n-2)_1),(3_1,(n-3)_2),\dots,((\frac{n-1}{2})_s,(\frac{n+1}{2})_t)|s=1 \text{ and } t=2 \text{ when } \frac{n-1}{2} \text{ is odd}\}\), and edges \(\{(n_1,1_2),(n_2,2_1),((n-1)_1,3_2),((n-2)_2,4_1),\dots,((\frac{n+3}{2})_s,(\frac{n+1}{2})_t)|s=1 \text{ and } t=2 \text{ when } \frac{n+3}{2} \text{ is even}\}\).

Page n-1: edges \(\{((n-1)_1,1_2),((n-2)_2,2_1),((n-3)_1,3_2),\dots,((\frac{n+1}{2})_s,(\frac{n-1}{2})_t)|s=1 \text{ and } t=2 \text{ when } \frac{n+1}{2} \text{ is even}\}\), and edges \(\{(1_1,n_2),(2_2,n_1),(3_1,(n-1)_2),(4_2,(n-2)_1)\dots,((\frac{n+1}{2})_s,(\frac{n+3}{2})_t)|s=1 \text{ and } t=2 \text{ when } \frac{n+3}{2} \text{ is odd}\}\).

It is clear that \(mbt(D) \leq n-1\). Therefore, the Kronecker cover of complete graph is dispersable when n is odd(see Fig.1 for the case n=5).

Fig.1 The matching book embedding of \(D(K_5)\)

Case 2. n is even

Let the vertex ordering on spine be as \(1_1, 2_2, 3_1, 4_2, \dots, (n-1)_1, n_2, n_1, (n-1)_2, (n-2)_1, (n-3)_2, \dots, 2_1, 1_2\). The matching book embedding of D in this case is given as follows:

Page 1: edges \(\{(i_1, j_2)|i-j=2; 3 \le i \le n-1, i \text{ is odd}\}\), edges \(\{(i_2, j_1)|i-j=2; 4 \le i \le n, i \text{ is even}\}\), and edges \(\{(1_1, 2_2), (n_1, (n-1)_2)\}\).

Page 2: edges \(\{(i_1, j_2)| j-i=2; 3 \leq j \leq n-1, j \text{ is odd}\}\), edges \(\{(i_2, j_1)| j-i=2; 4 \leq j \leq n, j \text{ is even}\}\), and edges \(\{(2_1, 1_2), ((n-1)_1, n_2)\}\).

Page 3: edges \(\{(i_1, j_2)|i-j=4; 5 \le i \le n-1, i \text{ is odd}\}\), edges \(\{(i_2, j_1)|i-j=4; 6 \le i \le n, i \text{ is even}\}\), and edges \(\{(1_1, 4_2), (2_2, 3_1), ((n-1)_2, (n-2)_1), (n_1, (n-3)_2)\}\).

Page 4: edges \(\{(i_1,j_2)|j-i=4; 5\leq j\leq n-1, i \text{ is odd}\}\), edges \(\{(i_2,j_1)|j-i=4; 6\leq j\leq n, i \text{ is even}\}\), and edges \(\{(4_1,1_2), (3_2,2_1), ((n-2)_2, (n-1)_1), ((n-3)_1, n_2)\}\).

Page n-3: edges \(\{(1_1,(n-2)_2),(2_2,(n-3)_1),(3_1,(n-4)_2),\dots,((\frac{n-2}{2})_s,(\frac{n}{2})_t)|s=1 \text{ and } t=2 \text{ when } \frac{n}{2} \text{ is even}\}\), and edges \(\{((n-1)_1,1_2),(n_2,2_1),(n_1,3_2),((n-1)_2,4_1),((n-2)_1,5_2),\dots,((\frac{n+4}{2})_s,(\frac{n+2}{2})_t)|s=1 \text{ and } t=2 \text{ when } \frac{n+4}{2} \text{ is even}\}\).

Page n-2: edges \(\{((n-2)_1, \overset{7}{1}_2), ((n-3)_2, 2_1), ((n-4)_1, 3_2), \dots, ((\frac{n}{2})_s, (\frac{n-2}{2})_t) | s = 1 \text{ and } t = 2 \text{ when } \frac{n}{2} \text{ is even} \}\), and edges \(\{(1_1, (n-1)_2), (2_2, n_1), (3_1, n_2), (4_2, (n-1)_1), (5_1, (n-2)_2), \dots, ((\frac{n+2}{2})_s, (\frac{n+4}{2})_t) | s = 1 \text{ and } t = 2 \text{ when } \frac{n+2}{2} \text{ is odd} \}\).

when \(\frac{1}{2}\) is even), and eages \(((\frac{1}{1}, (n-1)/2), (-2, n-1), (-1)/2)\), \((\frac{n+4}{2})_t)|s = 1\) and t = 2 when \(\frac{n+2}{2}\) is odd\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\). Page n-1: edges \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) and t = 1 when \(\frac{n}{2}\) is even\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\), and edges \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) and t = 2 when \(\frac{n}{2}\) is odd\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\).

Thus, \(mbt(D) \leq n-1\), the Kronecker cover of complete graph is dispersable when n is even(see Fig.2 for the case n=4).

Therefore, the result is established.

Lemma 3.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(G \square H)) \le mbt(D(G)) + \Delta(D(H))\).

Proof. Since D(H) is dispersable, there is a \(\Delta(D(H))\)-edge coloring of D(H) and a corresponding matching book embedding of D(H) in a \(\Delta(D(H))\)-page book so that all edges of one color

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 G✷H, and these vertices can be separated into p rows and q columns. Let the vertex set be {i^j |1 ≤ i ≤ p, 1 ≤ j ≤ q}, 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(G✷H). Assuming that both u¹ and u² in D(G✷H) correspond to the vertex u in G✷H. So

\[V(D(G \square H)) = \{i_{j_k} | 1 \le i \le p, 1 \le j \le q, k = 1, 2\}.\]

Dividing the vertices set of D(G✷H) 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(G✷H) corresponding to 2q|E(G)| edges of D(G) can all be matching book embedded in mbt(D(G)) pages.

The remaining 2p|E(H)| edges of D(G✷H) 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)) = ∆(D(H)), the edges of D(H) can also be matching book embedded in ∆(D(H)) pages.

Hence all edges of D(G✷H) can be matching book embedded in mbt(D(G)) + ∆(D(H)) pages(see Fig.3 for the case G = K3, H = C4).

Theorem 3.1. For \[p, q \geq 3\], \(mbt(D(K_p \square C_q)) = \Delta(D(K_p \square C_q)) = p + 1\).

Proof. Since ∆(D(Kp✷Cq)) = p + 1, mbt(D(Kp✷Cq)) ≥ p + 1 by Lemma 2.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✷Cq)) ≤ mbt(D(Kp))+∆(D(Cq)) = mbt(D(Kp))+2. Thus, by Lemma 3.2, we have mbt(D(Kp✷Cq)) ≤ p − 1 + 2 = p + 1. Therefore, mbt(D(Kp✷Cq)) = ∆(D(Kp✷Cq)), hence D(Kp✷Cq) is dispersable when p, q ≥ 3.

Fig.3 The matching book embedding of D(K3✷C4)

4. 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 K^p and cycles C^q is dispersable when p, q ≥ 3. By the results of Kainen and Overbay, the odd cycles and the complete graphs Kn(n ≥ 3) 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 graphs?

Acknowledgement

This work was partially funded by Science and Technology Project of Hebei Education Department, China (No. ZD2020130) and the Natural Science Foundation of Hebei Province, China (No. A2021202013).

References

[1] F. Bernhart and P.C. Kainen, The book thickness of a graph, Journal of Combinatorial Theory, Series B, 27 (1979), 320–331.

• [2] J.A.Bondy and U.S.R. Murty, Graph Theory, London: Springer, 2008.
• [3] W. Fulton, Covering spaces. In: Algebraic Topology. Graduate Texts in Mathematics, vol 153. Springer, New York, NY. 1995: 153–154.
• [4] P.C. Kainen, Complexity of products of even cycles, Bulletin of the Institute of Combinatorics and Its Applications 62 (2011), 95–102.
• [5] S. Overbay, Generalized Book Embeddings, Ph. D. thesis, Fort Collins: Colorado State University, 1998.
• [6] Z. Shao, H. Geng, and Z. Li, Matching book thickness of generalized Petersen graphs. Electronic Journal of Graph Theory and Applications 10 (1) (2022), 173–180.
• [7] Z. Shao, Y. Liu, and Z. Li, Matching book embedding of the cartesian product of a complete graph and a cycle, Ars Combinatoria, 153 (2020), 89–97.
• [8] Z. Shao, X. Yu, and Z. Li, On the dispersability of odd toroidal grids, Applied Mathematics and Computation, 453 (2023), 128087.
• [9] D. Waller, Double covers of graphs. Bulletin of the Australian Mathematical Society, 14 (2) (1976), 233–248.
• [10] J. Yang, Z. Shao, and Z. Li, Embedding cartesian product of some graphs in books, Communications in Mathematical Research 34(03) (2018), 253-260.