Electronic Journal of Graph Theory and Applications 14 .
, 205Ae214 The matching book embedding under some graph Zeling Shao.
Min Yao.
Zhiguo Li* Department of Mathematics.
Hebei University of Technology.
China zelingshao@163.
com, ym001209@163.
Zhiguolee@hebut.
* corresponding author Abstract 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.
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 G is placed on the spine, and each edge is placed on Received: 23 August 2025.
Revised: 11 February 2026.
Accepted: 1 March 2026.
The matching book embedding under some graph operations Zeling Shao et al.
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.
, book embedding theory has been extensively utilized in TSV placement.
, network topology visualization.
, genome sequence compression.
, and stack number computation.
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) = OI(G), nearly dispersable if mbt(G) = OI(G) 1.
Matching book embeddings have been extensively studied for various families of graphs.
In 1998.
Overbay proved the complete bipartite graph Kn,n .
Ou .
, even cycle C2n .
Ou .
, binary n-cube Q.
Ou .
and tree are dispersible.
In .
, it was proved that bt(H2G) O s mbt(H), bt(H y G) O 2q A mbt(H), and bt(H O G) O 2q A 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.
proved that mbt(Cp 2Cq ) = 4, when p, q are both even, and mbt(Cp 2Cq ) = 5, when p is even, q is odd.
In 2020.
Shao.
Liu.
Li.
established that for n, q Ou 3, mbt(Kn 2Cq ) = n(Kn 2Cq ) 1, which implies mbt(C3 2Cq ) = 5.
Joslin.
Kainen.
Overbay.
further proved in 2021 that mbt(C5 2Cq ) = 5.
In 2023.
Shao.
Yu.
Li.
obtained that mbt(Cp 2Cq ) = 5 when both p and q are odd and p Ou q Ou 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.
and pseudo-Halin graphs.
is obtained.
References .
respectively investigated the dispersibility of the circulant graphs C(Zn , .
, .
) and the Kronecker cover of the Cartesian product of complete graphs Kp and cycles Cq .
Recently.
Yuan.
Geng.
Yang.
Guan.
showed that mbt.
2Cn ) = 5, when n is even, and mbt.
2Cn ) = 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 Cm with m Ou 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.
Preliminaries In this section, we present some definitions and results which we needed in our work.
Definition 1.
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 Hi to vertex i of The matching book embedding under some graph operations Zeling Shao et al.
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 K4 C4 and C4 K4 ).
Fig.
1 (Lef.
K4 C4 .
(Righ.
C4 K4 .
Definition 2.
Let G and H be simple graphs.
The edge corona product G3H 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 Hi .
Definition 3.
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 (Gv H) = {.
i , hj ) | gi OO V (G), hj OO V (H)} and two vertices .
i , hj ) and .
k , hl ) are adjacent if and only if .
gi = gk and hj hl OO E(H), or .
gi gk OO E(G) and hj = hl = v.
Fig.
2 (Lef.
C4 3C4 .
(Righ.
C4 v C4 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.
If H is the subgraph of G, then mbt(H) O mbt(G).
The matching book embedding under some graph operations Zeling Shao et al.
Lemma 2.
Let G be a simple graph.
If G has an n-book matching embedding with printing cycle v1 , v2 , .
, vp , then G also has an n-book matching embedding with printing cycle v2 , v3 , .
, vp , v1 .
If G has an n-book matching embedding with printing cycle v1 , v2 , .
, vp , then G also has an n-book matching embedding Oe with printing cycle vp , .
, v2 , v1 .
Results for the Corona Product For a simple graph G with q vertices and a complete graph Kp , we assume that V (G Kp ) = { vi , uij | i = 1, 2, .
, q.
j = 1, 2, .
, p } and E(G Kp ) = E(G) O { uij , uik | i = 1, 2, .
, q.
j, k = 1, 2, .
, p.
j = .
O { .
i , uij ) | i = 1, 2, .
, q, j = 1, 2, .
, p }.
Next, we will compute the matching book thickness of the corona product between a dispersible graph and a simple graph.
Lemma 3.
Let G be an arbitrary dispersible graph with q vertices and n(G) = k, and let Kp be a complete graph.
Then.
G Kp is dispersible.
Proof.
According to n(G Kp ) = p k, then mbt(G Kp ) Ou n(G Kp ) by Lemma 2.
Because G is dispersible, without loss of generality, assume that v1 , v2 , .
, vq is the vertex order of the dispersible book embedding of G.
Then, we put the vertices of G Kp along the spine according to the following ordering of v1 , u11 , u12 , .
u1p , v2 , u21 , u22 , .
u2p , .
vq , uq1 , uq2 , .
Obviously, the edges of G can be matching book embedded in k pages named page 1, page p 2,.
, page k, and one of these k pages can place the edges { .
j , upOej 1 ) | 1 O i O q, 1 O j O 2 }, which do not cause influence on the matching book embedding of G.
The remaining edges of G Kp can be matching book embedded in additional p pages as follows.
Page k 1: edges { .
i , ui1 ) | 1 O i O q }, and edges { .
i1 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 1 }.
Page k 2: edges { .
i , ui2 ) | 1 O i O q }, and edges { .
i2 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 1 }.
Page k 3: edges { .
i , ui3 ) | 1 O i O q }, edges { .
i3 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 2 }, and edges { .
i1 , ui2 ) | 1 O i O q }.
Page k 4: edges { .
i , ui4 ) | 1 O i O q }, edges { .
i4 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 2 }, and edges { .
i1 , ui3 ) | 1 O i O q }.
Page k 5: edges { .
i , ui5 ) | 1 O i O q }, edges { .
i5 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 3 }, and edges { .
i1 , ui4 ), .
i2 , ui3 ) | 1 O i O q }.
Page k 6: edges { .
i , ui6 ) | 1 O i O q }, edges { .
i6 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 3 }, and edges { .
i1 , ui5 ), .
i2 , ui4 ) | 1 O i O q }.
Page k p Oe 3: edges { .
i , uipOe3 ) | 1 O i O q }, edges { .
ij , uipOe3Oej ) | 1 O i O q.
1 O j O p Oe 2 }.
and edges { .
ipOe2 , uip ) | 1 O i O q }.
Page k p Oe 2: edges { .
i , uipOe2 ) | 1 O i O q }, edges { .
ij , uipOe2Oej ) | 1 O i O q.
1 O j O p Oe 1 } and edges { .
ipOe1 , uip ) | 1 O i O q }.
The matching book embedding under some graph operations Zeling Shao et al.
Page k p Oe 1: edges { .
i , uipOe1 ) | 1 O i O q }, and edges { .
ij , uipOe1Oej ) | 1 O i O q.
1 O j O Oe 1 }.
Page k p: edges { .
i , uip ) | 1 O i O q }, and edges { .
ij , uipOej ) | 1 O i O q.
1 O j O p2 Oe1 }.
It is clear that we can construct a matching book embedding of G Kp in a .
-page book.
Hence, mbt (G Kp ) = n(Gq Kp ) = k p.
That is.
G Kp is dispersible.
(See Fig.
3 for the case C4 K4 and Fig.
4 for the case C6 K5 ).
p Fig.
3 The matching book embedding of C4 K4 .
Fig.
4 The matching book embedding of C6 K5 .
Theorem 3.
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 n(G H) = p n(G), then mbt(G H) Ou n(G H) by Lemma 2.
Since G H is the subgraph of G Kp , then mbt(G H) O mbt(G Kp ) by Lemma 2.
According to Lemma 3.
1 and n(G H) = n(G Kp ) = p n(G), then mbt(G H) = p n(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.
Let G be an arbitrary nearly dispersible graph with q vertices n(G) = k, and let Kp be a complete graph.
Then G Kp is dispersible.
The matching book embedding under some graph operations Zeling Shao et al.
Proof.
Firstly, mbt(GKp ) Ou n(GKp ) = k p by Lemma 2.
Further, we consider that GKp can be matching book embedded in p k pages.
According to G is a nearly dispersible graph, without loss of generality, assume that v1 , v2 , .
, vq is the vertex order corresponding to the nearly dispersible book embedding of G.
Then, put the vertices of G Kp along the spine according to the following ordering of v1 , u11 , u12 , .
u1p , v2 , u21 , u22 , .
u2p , .
vq , uq1 , uq2 , .
Obviously, the edges of G can be matching book embedded in k 1 pages named page p 1, page 2,.
, page k 1.
For 1 O i O q, the edge .
i , up ) and edges { .
j , upOej ) | 1 O j O 2 Oe 1 } can be placed on one of these k 1 pages where p d.
i ) = 0 in the matching book embedding of G, and the edges { .
j , upOej 1 ) | 1 O j O 2 } can be added to one of these k 1 pages where d.
i ) = 1 in the matching book embedding of G.
The remaining edges of G Kp can be embedded in additional p Oe 1 pages as follows.
Page k 2: edges { .
i , ui1 ) | 1 O i O q }, and edges { .
i1 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 1 }.
Page k 3: edges { .
i , ui2 ) | 1 O i O q }, and edges { .
i2 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 1 }.
Page k 4: edges { .
i , ui3 ) | 1 O i O q }, edges { .
i3 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 2 }, and edges { .
i1 , ui2 ) | 1 O i O q }.
Page k 5: edges { .
i , ui4 ) | 1 O i O q }, edges { .
i4 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 2 }, and edges { .
i1 , ui3 ) | 1 O i O q }.
Page k 6: edges { .
i , ui5 ) | 1 O i O q }, edges { .
i5 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 3 }, and edges { .
i1 , ui4 ), .
i2 , ui3 ) | 1 O i O q }.
Page k 7: edges { .
i , ui6 ) | 1 O i O q }, edges { .
i6 j , uipOej 1 ) | 1 O i O q.
1 O j O p Oe 3 }, and edges { .
i1 , ui5 ), .
i2 , ui4 ) | 1 O i O q }.
Page k p Oe 2: edges { .
i , uipOe3 ) | 1 O i O q }, edges { .
ij , uipOe3Oej ) | 1 O i O q.
1 O j O p Oe 2 }.
and edges { .
ipOe2 , uip ) | 1 O i O q }.
Page k p Oe 1: edges { .
i , uipOe2 ) | 1 O i O q }, edges { .
ij , uipOe2Oej ) | 1 O i O q.
1 O j O p Oe 1 } and edges { .
ipOe1 , uip ) | 1 O i O q }.
Page k p: edges { .
i , uipOe1 ) | 1 O i O q }, and edges { .
ij , uipOe1Oej ) | 1 O i O q.
1 O j O p Oe 1 }.
Hence, mbt (G Kp ) = n(Gq Kp ) = k p.
That is.
G Kp is dispersible.
(See Fig.
5 for the case K3 C7 and Fig.
6 for the case K5 C4 ).
Fig.
5 The matching book embedding of K3 C7 .
The matching book embedding under some graph operations Zeling Shao et al.
Fig.
6 The matching book embedding of K5 C4 .
Theorem 3.
Let G be an arbitrary nearly dispersible graph with q vertices, and let H be a simple graph with p vertices.
Then G H is dispersible.
Proof.
Firstly, since n(G H) = p n(G), mbt(G H) Ou n(G H) = p n(G) by Lemma In addition.
Since G H is the subgraph of G Kp , then mbt(G H) O mbt(G Kp ) by Lemma 2.
According to n(G H) = n(G Kp ) = p n(G), we conclude that G H is dispersible by Lemma 3.
Furthermore, the dispersibility of the edge corona product Cq 3H is given as follows.
Theorem 3.
Let Cq be a cycle and let H be a simple graph with p vertices, then Cq 3H is Proof.
Since n(Cq 3H) = 2p 2, then mbt(Cq 3H) Ou 2p 2 by Lemma 2.
Noting that Cq 3H is the subgraph of Cq 3Kp with n(Cq 3H) = n(Cq 3Kp ), then mbt(Cq 3H) O mbt(Cq 3Kp ) by Lemma 2.
Thus, it is sufficient to consider the matching book embedding of Cq 3Kp .
Assume that V (Cq 3Kp ) = { vi , uij | i = 1, 2, .
, q.
j = 1, 2, .
, p } and E(Cq 3Kp ) = E(Cq ) O { uij , uik | i = 1, 2, .
, q.
j, k = 1, 2, .
, p.
j = .
O { .
i , uij ) | i = 1, 2, .
, q, j = 1, 2, .
, p } O { .
i , uiOe1 j ) | i = 2, .
, q, j = 1, 2, .
, p } O { .
1 , uj ) | j = 1, 2, .
, p }.
Arrange the vertices of Cq 3Kp along the spine in the order v1 , u11 , u12 , .
u1p , v2 , u21 , u22 , .
u2p , .
vq , uq1 , uq2 .
Since Cq Kp induced by E(Cq ) O { uij , uik | i = 1, 2, .
, q.
j, k = 1, 2, .
, p.
j = .
O { .
i , uij ) | i = 1, 2, .
, q, j = 1, 2, .
, p } is the subgraph of Cq 3Kp , then, the edges of Cq Kp can be matching book embedded in p 2 pages by Theorem 3.
For 1 O j O p, { .
i , uiOe1 j ), .
1 , uj ) | i = 2, .
, q } can be assigned to additional distinctly p pages without crossing on a single page.
Cq Kp can be matching book embedded in 2p 2 pages.
Therefore.
Cq H is dispersible.
Results for the Comb Product By the definition of the comb product, we get the reult as follows.
The matching book embedding under some graph operations Zeling Shao et al.
Lemma 4.
For two simple graphs G.
H, mbt(G v H) Ou n(G v H) = max .
(G) dH .
, n(H)} Proof.
Since n(G v H) = max .
(G) dH .
, n(H)}, by Lemma 2.
1, mbt(G v H) Ou n(G v H) = max .
(G) dH .
, n(H)}.
Theorem 4.
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) Ou n(G v H) = max .
(G) dH .
, n(H)}.
Besause G and H are all dispersible, without loss of generality, assume that g1 , g2 , .
, gq and h1 , h2 , .
, hp is the vertex order respectively corresponding to the dispersible book embedding of G and H.
For G v H, assume that v = hj , then hj , hj 1 , .
, hp , h1 , h2 , .
, hjOe2 , hjOe1 is the vertex order corresponding to the dispersible book embedding of H by Lemma 2.
Put the vertices of Gv H on the spine in the ordering of .
1 , .
, .
1 , hj 1 ), .
, .
1 , hp ), .
1 , h1 ), .
1 , h2 ), , .
1 , hjOe1 ), .
2 , .
, .
2 , hj 1 ), .
, .
2 , hp ), .
2 , h1 ), .
2 , h2 ), .
, .
2 , hjOe1 ), .
, .
, .
q , .
, .
q , hj 1 ), .
, .
q , hp ), .
q , h1 ), .
q , h2 ), .
, .
q , hjOe1 ).
Next.
G v H can be matching book embedding in n(G v H) pages by considering two cases as follows.
Case 1.
n(G) dH .
> n(H).
Since H is dispersible, it admits a matching book embedding in n(H) pages.
Specificially, the edge set can be partitioned in to n(H) subsets Ei .
O i O n(H)), each assigned to a distinct page, such that for the vertex v, .
= 1 in Ei .
O i O dH .
), and .
= 0 in Ei .
H .
1 O i O n(H)).
Furthermore, let Ek,i .
O i O n(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 n(G) pages.
For each i.
H .
1 O i O n(H)), {Ek,i | 1 O k O |V (G)|} can be matching book embedded in the n(H) Oe dH .
pages of the n(G) pages according to n(G) > n(H) Oe dH .
For 1 O i O dH .
, the remaining edges {Ek,i | 1 O k O |V (G)|} can be placed in additional dH .
Therefore.
G v H can be matching book embedded in n(G) dH .
Case 2.
n(G) dH .
O n(H).
Since H is dispersible, |V (G)| copies H of G v H can be matching book embedded in n(H) Since n(G) O n(H) Oe dH .
, the edges of the graph G can be matching book embedded in n(G) pages selected from the n(H) pages where d(.
i , .
) = 0.
Therefore.
G v H can be matching book embedded in n(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.
Let G be an arbitrary nearly dispersible graph, and let H be an arbitrary dispersible Then.
G v H is dispersible, where v is a vertex of H and n(G) dH .
= n(H).
Theorem 4.
Let G be an arbitrary dispersible graph, and let H be an arbitrary nearly dispersible Then.
G v H is dispersible, where v is a vertex of H and n(G) dH .
= n(H).
The matching book embedding under some graph operations Zeling Shao et al.
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 Finally, the matching book thickness of the comb product of two dispersible graphs is Acknowledgment 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