Zeling Shao, Min Yao, Zhiguo Li*

Department of Mathematics, Hebei University of Technology, China

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

The matching book embedding of a graph G is an embedding of G with the vertices on the spine, and 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 embedding of G, denoted by mbt(G). In this paper, the exact matching book thickness of the corona product between a dispersible or nearly dispersible graph and a simple graph is determined. Additionally, the dispersibility of the edge product of a cycle and a simple graph is obtained. Finally the matching book thickness of the comb product of two dispersible graphs is obtained.

Keywords: matching book embedding, matching book thickness, corona product, comb product

Mathematics Subject Classification: 05C10

DOI: 10.5614/ejgta.2026.14.1.13

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 G is placed on the spine, and each edge is placed on

Received: 23 August 2025, Revised: 11 February 2026, Accepted: 1 March 2026.

^* corresponding author

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, denoted by bt(G).

Originally applied to VLSI routing algorithms[2], book embedding theory has been extensively utilized in TSV placement[3], network topology visualization[4], genome sequence compression[5] , and stack number computation[6]. Although determining the book thickness of a graph is an NPcomplete problem, the matching book thickness of graph provides a computable upper bound, thereby refining the page number estimation for book embedding.

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 a k page matching book embedding, denoted by mbt(G). A graph G is dispersable if mbt(G) = ∆(G), nearly dispersable if mbt(G) = ∆(G) + 1. Matching book embeddings have been extensively studied for various families of graphs. 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 dispersible[7]. In [12], it was proved that bt(H✷G) ≤ s + mbt(H), bt(H × G) ≤ 2q · mbt(H), and bt(H ⊠ G) ≤ 2q · mbt(H) + s + mbt(H), where H is a bipartite graph and G is a graph that admits a simultaneous s-stack q-queue layout. This finding establishes an upper bound for the book thickness of graph products by combining their matching book thickness, stack number, and queue number.

Significant progress has been made regarding the matching book thickness of the Cartesian product of two cycle. Kainen[13] proved that mbt(Cp✷Cq) = 4, when p, q are both even, and mbt(Cp✷Cq) = 5, when p is even, q is odd. In 2020, Shao, Liu, Li[14] established that for n, q ≥ 3, mbt(Kn✷Cq) = △(Kn✷Cq) + 1, which implies mbt(C3✷Cq) = 5. Joslin, Kainen, Overbay[15] further proved in 2021 that mbt(C5✷Cq) = 5. In 2023, Shao, Yu, Li[16] obtained that mbt(Cp✷Cq) = 5 when both p and q are odd and p ≥ q ≥ 7, which completely solves the problem about the dispersibility of the Cartesian product of two cycles. Additionally, the matching book thickness of generalized Petersen graphs[17] and pseudo-Halin graphs[18] is obtained. References [19] and [20] respectively investigated the dispersibility of the circulant graphs C(Zn, {1, k}) and the Kronecker cover of the Cartesian product of complete graphs K^p and cycles Cq. Recently, Yuan, Geng, Yang, Guan[21] showed that mbt(θm✷Cn) = 5, when n is even, and mbt(θm✷Cn) = 5 or 6, when n is odd, where θ^m is a uni-chord cycle obtained by adding an edge connecting two non-consecutive vertices from a cycle C^m with m ≥ 4.

In this paper, we obtain that matching book thickness of the corona product of a dispersible or nearly dispersible graph and a simple graph. Additionally, we get the dispersibility of the edge corona product between a cycle and an arbitrary graph. Finally, the matching book thickness of the comb product of two dispersible graphs is determined.

2. Preliminaries

In this section, we present some definitions and results which we needed in our work.

Definition 1. [10] Let G and H be simple graphs. The corona product G ◦ H of G and H is constructed as follows: Choose a labeling of the vertices of G with labels 1, . . . , m. Take one copy of G and m disjoint copies of H, labeled H1, . . . , Hm, and connect each vertex of Hⁱ to vertex i of G.

It follows the definition of the corona product that the G ◦ H is not in general isomorphic to H ◦ G. (See Fig.1 for the case K⁴ ◦ C⁴ and C⁴ ◦ K⁴ ).

Definition 2. [9] Let G and H be simple graphs. The edge corona product G✸H of G and H is constructed as follows: Choose a labeling of the edges of G with labels 1, . . . , m. Take one copy of G and m disjoint copies of H, labeled H1, . . . , Hm, and connect two endpoints of the edge i of G to all vertices of Hⁱ .

Definition 3. [11] Let v be a vertex of H. The comb product between G and H, denoted by G ✄^v H, is a graph obtained by taking one copy of G and V (G) copies H and identify the i-th copy of H at the vertex v with the i-th vertex of G.

By the definition of comb product, we say that V (G✄vH) = {(gⁱ , h^j ) | gⁱ ∈ V (G), h^j ∈ V (H)} and two vertices (gⁱ , h^j ) and (gk, hl) are adjacent if and only if

• (a) gⁱ = g^k and hjh^l ∈ E(H), or
• (b) gig^k ∈ E(G) and h^j = h^l = v.

Fig.2 (Left)C4✸C4. (Right)C⁴ ✄^v C⁴ .

Lemma 2.1. [3] For any simple graph G, ∆(G) ≤ χ ′ (G) ≤ mbt(G), where χ ′ (G) is the chromatic index of G. a

Lemma 2.2. [3] If H is the subgraph of G, then mbt(H) ≤ mbt(G).

Lemma 2.3. [1] Let G be a simple graph.

• (i) If G has an n-book matching embedding with printing cycle \(v_1, v_2, \ldots, v_p\), then G also has an n-book matching embedding with printing cycle \(v_2, v_3, \ldots, v_p, v_1\).
• (ii) If G has an n-book matching embedding \(\beta\) with printing cycle \(v_1, v_2, \ldots, v_p\), then G also has an n-book matching embedding \(\beta^-\) with printing cycle \(v_p, \ldots, v_2, v_1\).

3. Results for the Corona Product

For a simple graph G with q vertices and a complete graph \(K_p\), we assume that \(V(G \circ A)\)\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)

Next, we will compute the matching book thickness of the corona product between a dispersible graph and a simple graph.

Lemma 3.1. Let G be an arbitrary dispersible graph with q vertices and \(\triangle(G) = k\), and let \(K_p\)be a complete graph. Then, \(G \circ K_p\) is dispersible.

Proof. According to \(\triangle(G \circ K_p) = p + k\), then \(mbt(G \circ K_p) \ge \triangle(G \circ K_p)\) by Lemma 2.1. Because G is dispersible, without loss of generality, assume that \(v_1, v_2, \ldots, v_q\) is the vertex order of the dispersible book embedding of G. Then, we put the vertices of \(G \circ K_p\) along the spine according to the following ordering of \(v_1, u_1^1, u_2^1, \dots u_p^1, v_2, u_1^2, u_2^2, \dots u_p^2, \dots v_q, u_1^q, u_2^q, \dots u_p^q\). Obviously, the edges of G can be matching book embedded in k pages named page 1, page \(2, \ldots\), page k, and one of these k pages can place the edges \(\{\,(u^i_j,u^i_{p-j+1})\mid 1\leq i\leq q, 1\leq j\leq \left[\frac{p}{2}\right]\,\}\), which do not cause influence on the matching book embedding of G. The remaining edges of \(G \circ K_p\) can be matching book embedded in additional p pages as follows.

\text{Page }k+1\text{: edges }\{\,(v_i,u_1^i)\mid 1\leq i\leq q\,\}\text{, and edges }\{\,(u_{1+j}^i,u_{p-j+1}^i)\mid 1\leq i\leq q; 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq j\leq q, 1\leq 
|\frac{p}{2}| - 1.

Page k + 2: edges \(\{(v_i, u_2^i) \mid 1 \le i \le q\}\), and edges \(\{(u_{2+i}^i, u_{p-i+1}^i) \mid 1 \le i \le q; 1 \le j \le q\}\)\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)

Page k+3: edges \(\{(v_i, u_3^i) \mid 1 \le i \le q\}\), edges \(\{(u_{3+i}^i, u_{n-i+1}^i) \mid 1 \le i \le q; 1 \le j \le q\}\)\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\), and edges \(\{ (u_1^i, u_2^i) \mid 1 \le i \le q \}\).

Page k+4: edges \(\{(v_i,u_4^i) \mid 1 \leq i \leq q\}\), edges \(\{(u_{4+j}^i,u_{p-j+1}^i) \mid 1 \leq i \leq q; 1 \leq j \leq q\}\)\(\left[\frac{p}{2}\right] - 2\), and edges \(\{(u_1^i, u_3^i) \mid 1 < i < q\}\).

Page k + 5: edges \(\{(v_i, u_5^i) \mid 1 \le i \le q\}\), edges \(\{(u_{5+j}^i, u_{p-j+1}^i) \mid 1 \le i \le q; 1 \le j \le q\}\)\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\), and edges \(\{ (u_1^i, u_4^i), (u_2^i, u_3^i) \mid 1 \le i \le q \}\).

Page k+6: edges \(\{(v_i,u_6^i) \mid 1 \le i \le q\}\), edges \(\{(u_{6+j}^i,u_{p-j+1}^i) \mid 1 \le i \le q; 1 \le j \le q\}\)\(\left[\frac{p}{2}\right] - 3\), and edges \(\{(u_1^i, u_5^i), (u_2^i, u_4^i) \mid 1 \le i \le q\}\).

Page k + p - 3: edges \(\{(v_i, u_{p-3}^i) \mid 1 \le i \le q\}\), edges \(\{(u_j^i, u_{p-3-j}^i) \mid 1 \le i \le q; 1 \le j \le q\}\)\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) and edges \(\{ \, (u^i_{p-2}, u^i_p) \mid 1 \leq i \leq q \, \}.\)Page k+p-2: edges \(\{(v_i,u_{p-2}^i) \mid 1 \leq i \leq q\}\), edges \(\{(u_j^i,u_{p-2-j}^i) \mid 1 \leq i \leq q; 1 \leq j \leq q\}\)

\(\left[\frac{p}{2}\right] - 1\) and edges \(\{(u_{p-1}^i, u_p^i) \mid 1 \le i \le q\}.\)

Page k + p − 1: edges { (vⁱ , uⁱ p−1 ) | 1 ≤ i ≤ q }, and edges { (u i j , uⁱ p−1−j ) | 1 ≤ i ≤ q; 1 ≤ j ≤ p 2 − 1 }.

Page k+p: edges { (vⁱ , uⁱ p ) | 1 ≤ i ≤ q }, and edges { (u i j , uⁱ p−j ) | 1 ≤ i ≤ q; 1 ≤ j ≤ p 2 −1 }. It is clear that we can construct a matching book embedding of G ◦ K^p in a (k + p)-page book. Hence, mbt(G ◦ Kp) = △(G^q ◦ Kp) = k + p. That is, G ◦ K^p is dispersible. (See Fig.3 for the case C⁴ ◦ K⁴ and Fig.4 for the case C⁶ ◦ K5).

Fig.3 The matching book embedding of C⁴ ◦ K4.

Fig.4 The matching book embedding of C⁶ ◦ K5.

Theorem 3.1. Let G be an arbitrary dispersible graph with q vertices, and let H be a simple graph with p vertices. Then G ◦ H is dispersible.

Proof. According to △(G◦H) = p+△(G), then mbt(G◦H) ≥ △(G◦H) by Lemma 2.1. Since G ◦ H is the subgraph of G ◦ Kp, then mbt(G ◦ H) ≤ mbt(G ◦ Kp) by Lemma 2.2. According to Lemma 3.1 and △(G ◦ H) = △(G ◦ Kp) = p + △(G), then mbt(G ◦ H) = p + △(G).

Therefore, G ◦ H is dispersible.

Next, we will show that the corona product between a nearly dispersible graph and a simple graph is dispersible.

Lemma 3.2. Let G be an arbitrary nearly dispersible graph with q vertices △(G) = k, and let K^p be a complete graph. Then G ◦ K^p is dispersible.

Proof. Firstly, \(mbt(G \circ K_p) \geq \triangle(G \circ K_p) = k+p\) by Lemma 2.1. Further, we consider that \(G \circ K_p\) can be matching book embedded in p+k pages. According to G is a nearly dispersible graph, without loss of generality, assume that \(v_1, v_2, \ldots, v_q\) is the vertex order corresponding to the nearly dispersible book embedding of G. Then, put the vertices of \(G \circ K_p\) along the spine according to the following ordering of \(v_1, u_1^1, u_2^1, \ldots u_p^1, v_2, u_1^2, u_2^2, \ldots u_p^2, \ldots u_p^2, \ldots u_q^q, u_1^q, u_2^q, \ldots u_p^q\). Obviously, the edges of G can be matching book embedded in k+1 pages named page 1, page 2,..., page k+1. For \(1 \leq i \leq q\), the edge \((v_i, u_p^i)\) and edges \(\{(u_j^i, u_{p-j}^i) \mid 1 \leq j \leq \lceil \frac{p}{2} \rceil - 1\}\) can be placed on one of these k+1 pages where \(d(v_i)=0\) in the matching book embedding of G, and the edges \(\{(u_j^i, u_{p-j+1}^i) \mid 1 \leq j \leq \lceil \frac{p}{2} \rceil \}\) can be added to one of these k+1 pages where \(d(v_i)=1\) in the matching book embedding of G. The remaining edges of \(G \circ K_p\) can be embedded in additional p-1 pages as follows.

Page k + 2: edges \(\{(v_i, u_1^i) \mid 1 \le i \le q\}\), and edges \(\{(u_{1+j}^i, u_{p-j+1}^i) \mid 1 \le i \le q; 1 \le j \le \lceil \frac{p}{2} \rceil - 1\}\).

Page k + 3: edges \(\{(v_i, u_2^i) \mid 1 \le i \le q\}\), and edges \(\{(u_{2+j}^i, u_{p-j+1}^i) \mid 1 \le i \le q; 1 \le j \le \lfloor \frac{p}{2} \rfloor - 1\}\).

Page k+4: edges \(\{(v_i,u_3^i) \mid 1 \leq i \leq q\}\), edges \(\{(u_{3+j}^i,u_{p-j+1}^i) \mid 1 \leq i \leq q; 1 \leq j \leq \lceil \frac{p}{2} \rceil - 2\}\), and edges \(\{(u_1^i,u_2^i) \mid 1 \leq i \leq q\}\).

Page k + 5: edges \(\{(v_i, u_4^i) \mid 1 \le i \le q\}\), edges \(\{(u_{4+j}^i, u_{p-j+1}^i) \mid 1 \le i \le q; 1 \le j \le \lfloor \frac{p}{2} \rfloor - 2\}\), and edges \(\{(u_1^i, u_3^i) \mid 1 \le i \le q\}\).

Page k+6: edges \(\{(v_i,u_5^i) \mid 1 \leq i \leq q\}\), edges \(\{(u_{5+j}^i,u_{p-j+1}^i) \mid 1 \leq i \leq q; 1 \leq j \leq \lfloor \frac{p}{2} \rfloor - 3\}\), and edges \(\{(u_1^i,u_4^i),(u_2^i,u_3^i) \mid 1 \leq i \leq q\}\).

Page k+7: edges \(\{(v_i,u_6^i) \mid 1 \leq i \leq q\}\), edges \(\{(u_{6+j}^i,u_{p-j+1}^i) \mid 1 \leq i \leq q; 1 \leq j \leq \lfloor \frac{p}{2} \rfloor - 3\}\), and edges \(\{(u_1^i,u_5^i),(u_2^i,u_4^i) \mid 1 \leq i \leq q\}\).

Page k + p - 2: edges \(\{(v_i, u_{p-3}^i) \mid 1 \le i \le q\}\), edges \(\{(u_j^i, u_{p-3-j}^i) \mid 1 \le i \le q; 1 \le j \le \lceil \frac{p}{2} \rceil - 2\}\). and edges \(\{(u_{p-2}^i, u_p^i) \mid 1 \le i \le q\}\).

Page k+p-1: edges \(\{(v_i,u_{p-2}^i) \mid 1 \leq i \leq q\}\), edges \(\{(u_j^i,u_{p-2-j}^i) \mid 1 \leq i \leq q; 1 \leq j \leq \lfloor \frac{p}{2} \rfloor - 1\}\) and edges \(\{(u_{p-1}^i,u_p^i) \mid 1 \leq i \leq q\}\).

Page k + p: edges \(\{(v_i, u_{p-1}^i) \mid 1 \le i \le q\}\), and edges \(\{(u_j^i, u_{p-1-j}^i) \mid 1 \le i \le q; 1 \le j \le \lfloor \frac{p}{2} \rfloor - 1\}\).

Hence, \(mbt(G \circ K_p) = \triangle(G_q \circ K_p) = k + p\). That is, \(G \circ K_p\) is dispersible. (See Fig.5 for the case \(K_3 \circ C_7\) and Fig.6 for the case \(K_5 \circ C_4\)).

Fig.5 The matching book embedding of \(K_3 \circ C_7\).

Theorem 3.2. Let G be an arbitrary nearly dispersible graph with q vertices, and let H be a simple graph with p vertices. Then \(G \circ H\) is dispersible,

Proof. Firstly, since \(\triangle(G \circ H) = p + \triangle(G)\), \(mbt(G \circ H) \geq \triangle(G \circ H) = p + \triangle(G)\) by Lemma 2.1. In addition, Since \(G \circ H\) is the subgraph of \(G \circ K_p\), then \(mbt(G \circ H) \leq mbt(G \circ K_p)\) by Lemma 2.2. According to \(\triangle(G \circ H) = \triangle(G \circ K_p) = p + \triangle(G)\), we conclude that \(G \circ H\) is dispersible by Lemma 3.2.

Furthermore, the dispersibility of the edge corona product \(C_q \diamondsuit H\) is given as follows.

Theorem 3.3. Let \(C_q\) be a cycle and let H be a simple graph with p vertices, then \(C_q \diamondsuit H\) is dispersible.

Proof. Since \(\triangle(C_q \diamondsuit H) = 2p + 2\), then \(mbt(C_q \diamondsuit H) \ge 2p + 2\) by Lemma 2.1. Noting that \(C_q \diamondsuit H\) is the subgraph of \(C_q \diamondsuit K_p\) with \(\triangle(C_q \diamondsuit H) = \triangle(C_q \diamondsuit K_p)\), then \(mbt(C_q \diamondsuit H) \le mbt(C_q \diamondsuit K_p)\) by Lemma 2.2. Thus, it is sufficient to consider the matching book embedding of \(C_q \diamondsuit K_p\).

Assume that \(V(C_q \diamondsuit K_p) = \{v_i, u_j^i \mid i=1,2,\ldots,q; j=1,2,\ldots,p\}\) and \(E(C_q \diamondsuit K_p) = E(C_q) \cup \{u_j^i, u_k^i \mid i=1,2,\ldots,q; j,k=1,2,\ldots,p; j\neq k\} \cup \{(v_i,u_j^i) \mid i=1,2,\ldots,q, j=1,2,\ldots,p\} \cup \{(v_i,u_j^i) \mid i=2,\ldots,q, j=1,2,\ldots,p\} \cup \{(v_1,u_j^q) \mid j=1,2,\ldots,p\}.\) Arrange the vertices of \(C_q \diamondsuit K_p\) along the spine in the order \(v_1,u_1^1,u_2^1,\ldots u_p^1,v_2,u_1^2,u_2^2,\ldots u_p^2,\ldots u_q,u_1^q,u_2^q,\ldots u_p^q\). Since \(C_q \diamondsuit K_p\) induced by \(E(C_q) \cup \{u_j^i,u_k^i \mid i=1,2,\ldots,q; j,k=1,2,\ldots,p; j\neq k\} \cup \{(v_i,u_j^i) \mid i=1,2,\ldots,q,j=1,2,\ldots,p\}\) is the subgraph of \(C_q \diamondsuit K_p\), then, the edges of \(C_q \diamondsuit K_p\) can be matching book embedded in p+2 pages by Theorem 3.2. For \(1\leq j\leq p\), \(\{(v_i,u_j^{i-1}),(v_1,u_j^q) \mid i=2,\ldots,q\}\) can be assigned to additional distinctly p pages without crossing on a single page. \(C_q \rhd K_p\) can be matching book embedded in 2p+2 pages. Therefore, \(C_q \rhd H\) is dispersible.

4. Results for the Comb Product

By the definition of the comb product, we get the reult as follows.

Lemma 4.1. For two simple graphs G, H,

\[mbt(G \rhd_v H) \ge \triangle(G \rhd_v H) = max \{\triangle(G) + d_H(v), \triangle(H)\}\]

.

Proof. Since \[\triangle(G \rhd_v H) = max\{\triangle(G) + d_H(v), \triangle(H)\}\], by Lemma 2.1, \(mbt(G \rhd_v H) \ge \triangle(G \rhd_v H) = max\{\triangle(G) + d_H(v), \triangle(H)\}\).

Theorem 4.1. Let G be an arbitrary dispersible graph with q vertices, and let H be an arbitrary dispersible graph with p vertices. Then, G ✄^v H is dispersible, where v is a vertex of H.

Proof. According to Lemma 4.1, mbt(G ✄^v H) ≥ △(G ✄^v H) = max {△(G) + dH(v), △(H)}. Besause G and H are all dispersible, without loss of generality, assume that g1, g2, . . . , g^q and h1, h2, . . . , h^p is the vertex order respectively corresponding to the dispersible book embedding of G and H. For G ✄^v H, assume that v = h^j , then h^j , hj+1, . . . , hp, h1, h2, . . . , hj−2, hj−¹ is the vertex order corresponding to the dispersible book embedding of H by Lemma 2.3. Put the vertices of G✄^v H on the spine in the ordering of (g1, v), (g1, hj+1), . . . , (g1, hp), (g1, h1), (g1, h2), . . . , (g1, hj−1), (g2, v), (g2, hj+1), . . . , (g2, hp), (g2, h1), (g2, h2), . . . , (g2, hj−1), . . . , . . . , (gq, v), (gq, hj+1), . . . , (gq, hp), (gq, h1), (gq, h2), . . . , (gq, hj−1), Next, G ✄^v H can be matching book embedding in △(G ✄^v H) pages by considering two cases as follows.

Case 1. \[\triangle(G) + d_H(v) > \triangle(H)\].

Since H is dispersible, it admits a matching book embedding in △(H) pages. Specificially, the edge set can be partitioned in to △(H) subsets Ei(1 ≤ i ≤ △(H)), each assigned to a distinct page, such that for the vertex v,

• (1). d(v) = 1 in Ei(1 ≤ i ≤ dH(v)), and
• (2). d(v) = 0 in Ei(dH(v) + 1 ≤ i ≤ △(H)).

Furthermore, let Ek,i(1 ≤ i ≤ △(H)) denote all edges of the k-th copy of H in the graph G ✄^v H.

Since G is dispersible, G can be matching book embedded in △(G) pages. For each i(dH(v) + 1 ≤ i ≤ △(H)), {Ek,i | 1 ≤ k ≤ |V (G)|} can be matching book embedded in the △(H) − dH(v) pages of the △(G) pages according to △(G) > △(H)−dH(v). For 1 ≤ i ≤ dH(v), the remaining edges {Ek,i | 1 ≤ k ≤ |V (G)|} can be placed in additional dH(v) pages.

Therefore, G ✄^v H can be matching book embedded in △(G) + dH(v) pages.

Case 2. \[\triangle(G) + d_H(v) \leq \triangle(H)\].

Since H is dispersible, |V (G)| copies H of G ✄^v H can be matching book embedded in △(H) pages. Since △(G) ≤ △(H) − dH(v), the edges of the graph G can be matching book embedded in △(G) pages selected from the △(H) pages where d((gⁱ , v)) = 0.

Therefore, G ✄^v H can be matching book embedded in △(H) pages.

Using the similar method, we obtain that the dispersibility of the comb product between a dispersible graph and a nearly dispersible graph as follows.

Theorem 4.2. Let G be an arbitrary nearly dispersible graph, and let H be an arbitrary dispersible graph. Then, G ✄^v H is dispersible, where v is a vertex of H and △(G) + dH(v) ̸= △(H).

Theorem 4.3. Let G be an arbitrary dispersible graph, and let H be an arbitrary nearly dispersible graph. Then, G ✄^v H is dispersible, where v is a vertex of H and △(G) + dH(v) ̸= △(H).

5. Conclusions

In this paper, we study the matching book embedding of the corona product formed by a dispersible or nearly dispersible graph and a simple graph, and get the exact matching book thickness of the corona product of a dispersible or nearly dispersible graph and an arbitrary graph. Furthermore, the dispersibility of the edge corona product between a cycle and a simple graph is determined. Finally, the matching book thickness of the comb product of two dispersible graphs is obtained.

Acknowledgment

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] F.R.K. Chung, F.T. Leighton, and A.L. Rosenberg, Embedding graphs in books: a layout problem with applications to VLSI design, SIAM Journal on Algebraic Discrete Methods, 8(1)(1987), 33-58.
• [3] N. Khan, V.S. Rao, and S. Lim, Development of 3-D silicon module with TSV for system in packaging, IEEE Transactions on Components and Packaging Technologies, 33(1)(2020), 3-9.
• [4] B. Zhao, W. Chen, J. Meng, and F. Liu, Book embedding of complex network with community structure, Applied Mathematics and Computation, 361(2019),747-751.
• [5] W. Liang, Human Genome Book: Words, Sentences and Paragraphs, arXiv preprint arXiv:2501.16982.
• [6] X. Guan, C. Wu, W. Yang, and J. Meng, A survey on book-embedding of planar graphs[J]. Frontiers of Mathematics in China, 17(2)(2022), 255-273.
• [7] S.B. Overbay, Generalized Book Embeddings, Colorado State University, 1998.
• [8] C. McLeman and E. McNicholas, Spectra of coronae, Linear algebra and its applications, 435(5)(2011), 998-1007.
• [9] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Publishing Company, Incorporated, 2008.
• [10] S. Nada, A. Elrokh, E.A.Elsakhawi, and D.E. Sabra, The corona between cycles and paths, Journal of the Egyptian Mathematical Society, 25(2)(2017), 111-118.

• [11] S.W. Saputro, N. Mardiana, and I.A. Purwasih, The metric dimension of comb product graphs, Matematicki vesnik, 69(4) (2017), 248-258.
• [12] S. Pupyrev, Book embeddings of graph products, arxiv preprint arxiv:2007.15102.
• [13] P.C. Kainen, Complexity of products of even cycles, Bull. Inst. Combin. Applic, 62(2011), 95–102.
• [14] Z.L. Shao, Y.Q. Liu, and Z.G. Li, Matching book embedding of the cartesian product of a complete graph and a cycle, Ars Combinatoria, 153 (2020), 89–97.
• [15] S.S. Joslin, P.C. Kainen, and S. Overbay, On dispersability of some products of cycles, Missouri J. Math. Sci, 33(2)(2021), 206–213.
• [16] Z.L. Shao, X.X. Yu, and Z.G. Li, On the dispersability of odd toroidal grids, Applied Mathematics and Computation, 453 (2023), 128087.
• [17] Z.L. Shao, H.R. Geng, Z.G. Li, Matching book thickness of generalized Petersen graphs, Electronic Journal of Graph Theory and Applications, 10(1)(2022), 173-180.
• [18] Z.L. Shao, H.R. Geng, Z.G. Li, The matching book embeddings of pseudo-Halin graphs, Electronic Journal of Graph Theory and Applications, 11(1)(2023), 317-327.
• [19] X.X. Yu, Z.L. Shao, and Z.G. Li, On the classification and dispersability of circulant graphs with two jump lengths, Discrete Applied Mathematics, 355(2024), 268-286.
• [20] Z.L. Shao, Y.Q. Cui, and Z.G. Li, The dispersability of the Kronecker cover of the product of complete graphs and cycles, Electronic Journal of Graph Theory and Applications, 12(1)(2024), 117-123.
• [21] Y. Yuan, X. Geng, W. Yang, and X. Guan, A Note on Matching Book Embedding of the Cartesian Product of a Uni-chord Cycle and a Cycle, Journal of Interconnection Networks, (2025), 2550011.