Electronic Journal of Graph Theory and Applications 10 .
, 173Ae180 Matching book thickness of generalized Petersen Zeling Shao.
Huiru Geng.
Zhiguo LiO Department of Mathematics.
Hebei University of Technology.
China zelingshao@163.
com, genghuiru2021@163.
Zhiguolee@hebut.
Corresponding author.
Abstract The matching book embedding of a graph G is to place its vertices on the spine, and arrange its edges on the pages so that the edges in the same page do not intersect each other and the edges induced subgraphs of each page are 1-regular.
The matching book thickness of G is the minimum number of pages required for any matching book embedding of G, denoted by mbt(G).
In this paper, the matching book thickness of generalized Petersen graphs is determined.
Keywords: matching book embedding, matching book thickness, generalized Petersen graph Mathematics Subject Classification : 05C10.
68R10
DOI: 10.
5614/ejgta.
Introduction The book embedding of a graph was first introduced by Bernhart and Kainen .
The book embedding problem of a graph consists of arranging the vertices on the spine .
in order and placing the edges in the pages .
he half planes with the spine as the common boundar.
, so that the edges in the same page do not intersect each other.
The book thickness of a graph G is the least number of pages that G can be embedded under all vertex orders, denoted by bt(G).
On the basis of book embedding, an additional condition is added that the edge induced subgraphs on each page are 1-regular, which is called matching book embedding.
The matching book thickness of G is the minimum number of pages that G can be matching embedded, denoted by mbt(G).
The graph G is Received: 3 September 2021.
Revised: 23 January 2022.
Accepted: 13 February 2022.
Matching book thickness of generalized Petersen graphs Zeling Shao et al.
said to be dispersable if it has a matching book embedding in OI(G) pages, i.
mbt(G) = OI(G), where OI(G) is the maximum degree of G.
The book embedding of graphs have numerous applications.
Reference .
and its references study the book embedding of some graphs, and obtain the book thickness of graphs.
But there are few conclusions about the matching book thickness of graphs, especially the exact Bernhart and Kainen .
proposed that complete bipartite graphs Kn,n .
Ou .
, even cycles C2n .
Ou .
, binary n-cube Q.
Ou .
and trees are dispersable and Overbay .
gave detailed proof.
For cartesian product graphs.
Kainen .
and Shao.
Liu and Li .
obtained that the matching book thickness of Cm y Cn .
is eve.
and Km y Cn .
, n Ou .
, respectively.
Kainen and Overbay showed that cubic planar bipartite graphs are dispersable .
For a Halin graph H.
Shao.
Geng, and Li .
proved that mbt(H) = 4, if OI(H) = 3 and mbt(H) = OI(H), if OI(H) Ou 4.
The generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon.
These graphs were first defined by Watkins .
The generalized Petersen graph P .
, .
, n Ou 3 and 1 O k O n Oe 1, has vertex-set .
, i | i = 1, 2, .
, .
and edge-set {.
, i .
, .
, .
), .
, i ) | i = 1, 2, .
, .
( mod .
The generalized Petersen graph P .
, .
is always a 3-regular graph with 2n vertices and 3n edges, and P .
, .
is the well known Petersen graph, it can be matching embedded in a 4-page book .
ee Figure .
From the definition of P .
, .
P .
, .
O = P .
, n Oe .
for k < n2 , thus we can assume 1 O k < n2 .
Figure 1.
P .
, .
and the matching book embedding of P .
, .
In this paper, we obtain that the matching book thickness of a generalized Petersen graph P .
, .
as follows.
Main Theorem:
mbt(P .
, .
) = 3, n is even and k is odd, 4, else.
The Proof of Main Theorem The proof will be completed by a sequence of lemmas.
Lemma 2.
For any simple graph G.
OI(G) O N0 (G) O mbt(G), where N0 (G) is the chromatic index of G.
Matching book thickness of generalized Petersen graphs Zeling Shao et al.
Lemma 2.
For a regular graph G.
G is dispersable only if G is bipartite.
Suppose X = .
1 , .
, xi } is an ordered vertex set with i vertices in P .
, .
, we define X 0 := .
01 , .
, x0i } and X Oe1 := .
i , .
, x1 }, and call them paired ordering of X and reverse ordering of X, respectively.
Lemma 2.
If P .
, .
is a generalized Petersen graph, n is even and 1 O k < n2 , then 3, k is odd, mbt(P .
, .
) = 4, k is even.
Proof.
According to the parity of k, we need to consider two cases to prove the matching book thickness of P .
, .
Case 1.
k is odd.
Since OI(P .
, .
) = 3, mbt(P .
, .
) Ou 3 by Lemma 2.
Now we embed the vertices of P .
, .
along the spine according to the following ordering of 1, n, 3, n Oe 2, .
, n Oe 3, 4, n Oe 1, 2, 2 , .
Oe .
, 4 , .
Oe .
, .
Oe .
, 3 , n , 1 .
All edges of P .
, .
can be placed on 3 pages in a matching manner as follows.
Page 1: edges {.
, i .
, .
, .
) | 1 O i O n, i is od.
Page 2: edges {.
, i .
, .
, .
) | 1 O i O n, i is eve.
Page 3: edges {.
, i ) | 1 O i O .
Hence mbt(P .
, .
) O 3.
(See Figure 2.
for the case k = 3 and n = .
Case 2.
k is even.
In this case.
P .
, .
is 3-regular but not bipartite because it contains at least one odd cycle.
According to Lemma 2.
P .
, .
is not dispersable, mbt(P .
, .
) Ou OI(P .
, .
) 1 = 4.
Let d = gcd.
, .
be the greatest common denominator of n and k .
ere n and k are even, so d is eve.
Ei is an ordered vertex set and Ei = .
, i k, i 2k, .
, i ( nd Oe .
O i O .
, then V (P .
, .
) = di=1 Ei Ei .
We put all vertices on the spine in the ordering E1 .
E2Oe1 , .
EdOe1 .
EdOe1 , (EdOe1 ) , (EdOe1 ) , .
, (E2Oe1 ) , (E1 ) and assign the edges of P .
, .
to 4 pages as follows.
Page 1: edges {.
Oe i ak, n Oe i .
| 1 O i O d, 0 O a O nd Oe 2, a is eve.
and edges {.
, .
) | 1 O i O n, i is od.
Page 2: edges {.
Oe i ak, n Oe i .
| 1 O i O d, 0 O a O nd Oe 2, a is od.
and edges {(.
, .
) | 0 O j O .
, where b = min.
OO Z | d ck O n Oe k .
Page 3: edges {.
Oe i Oe k, n Oe .
| 1 O i O .
, edges {(.
, .
) | 1 O i < d, i is even, 0 O j O nd Oe .
and edges {(.
, .
) | b 1 O j O Oe .
, where b = min.
OO Z | d ck O n Oe k .
Page 4: edges {.
, i ) | 1 O i O .
Therefore we get a matching book embedding of P .
, .
in a 4-page book, mbt(P .
, .
) O 4.
(See Figure 2.
for the case k = 4 and n = .
The result is established.
Matching book thickness of generalized Petersen graphs Zeling Shao et al.
Figure 2.
The matching book embedding of P .
, .
and P .
, .
Lemma 2.
If P .
, .
is a generalized Petersen graph, n is odd and 1 O k < n2 , then mbt(P .
, .
) = OI(P .
, .
) 1 = 4.
Proof.
Since n is odd.
P .
, .
contains an odd cycle Cn according to its definition, it is not bipartite, and then P .
, .
is 3-regular, so it is not dispersible by Lemma 2.
2, mbt(P .
, .
) Ou OI(P .
, .
) 1 = 4.
Let n = ak r .
Ou 2, 0 O r < .
Ai .
Bi .
Ci and Di be ordered vertex set.
Ai = .
, i nOe.
O i O .
Bi = .
k, ik Oe 1, .
, ik Oe .
Oe .
} .
O i O .
Ci = .
k Oe i, ak Oe i Oe .
O i O k Oe .
Di = .
k 1, ik 2, .
, ik .
O i O .
According to the parity of a, we need to consider two cases to prove that mbt(P .
k r, .
) O 4 as follows.
Case 1.
a is even.
(Oe.
i 1 It is easy to know that r is odd because n is odd and a is even.
Assume 1 = ki=kOer 1 Ai (Oe.
i 1 (Oe.
kOer 2 (Oe.
kOer 3 (Oe.
k 1 Oe1 Oe1 =B2 .
B3 , .
BaOe1 .
Ba .
i1 = .
, 2, .
AkOer 1 .
AkOer 2 , .
Ak 2 = i=2 Bi Oe1 k Oe r, 1 , 2 }.
Now we can construct a matching book embedding of P .
k r, .
in a 4-page book as follows.
Put all 2n vertices on the spine in the ordering i1 .
Oe1 1 ) and assign all edges to 4 Page 1: edges {.
jk, i jk .
| 1 O i O k, 0 O j O a Oe 1, j is eve.
and edges {.
, .
), .
, .
) | 1 O i O 2k, i is odd, 2k O j O ak, j is even and j 6= b.
, where 1 O b O a and b is even.
Page 2: edges {.
Oe i Oe k, n Oe .
| 0 O i O r Oe .
and edges {.
, .
), .
, .
) | 1 O i O 2k Oe 1, i is even, 2k O j O n, j is od.
Page 3: edges {.
Oe i, n Oe .
, .
k Oe i, jk Oe i .
| 0 O i O k Oe 1, 1 O j O a Oe 1, j is eve.
and edges {(.
, .
k i .
), (.
, .
) | 1 O i O r, i is even, 2 O j O a, j is eve.
Page 4: edges {.
, i ) | 1 O i O .
Hence mbt(P .
k r, .
) O 4.
(See Figure.
for the case a = 2, k = 4 and r = .
Case 2.
a is odd.
In this case, we prove mbt(P .
k r, .
) O 4 from the following two situations.
k is even and r is odd.
Matching book thickness of generalized Petersen graphs Zeling Shao et al.
QkOe1 (Oe.
i 1 (Oe.
i 1 Oe1 = AOe1 kOer 1 .
AkOer 2 , .
AkOe1 .
Ak .
i=kOer 1 Ai i=0 Ci (Oe.
aOe3 Oe1 Oe1 C0Oe1 .
C1 , .
CkOe2 .
CkOe1 .
3 = i=1 Di = D1 .
D2Oe1 , .
DaOe4 .
DaOe3 i2 = .
, 2, .
, k Oe Oe1 r, 1 , 2 , 3 }.
All 2n vertices of P .
k r, .
are assigned on the spine by the ordering of i2 .
Oe1 We denote 1 = and all edges of P .
k r, .
can be matching embedded in a 4-page book as follows.
Page 1: edges {.
jk, i jk .
| 1 O i O k, 0 O j O a Oe 3, j is eve.
and edges {.
, .
), .
, .
) | 1 O i O 3k, i is odd, 3k 1 O j O ak Oe 1, j is even and j 6= b.
, where 3 < b < a, b is odd.
Page 2: edges {.
Oe i Oe k, n Oe .
| 0 O i O k Oe .
and edges {.
, .
), .
, .
) | 1 O i O 3k Oe 1, i is even, 3k O j O n, j is od.
Page 3: edges {.
Oe i, n Oe .
, .
k Oe i, jk Oe i .
| 0 O i O k Oe 1, 1 O j O a Oe 2, j is eve.
, edges {(.
Oe .
k i, .
Oe .
k i .
| 1 O i O .
and edges {(.
, .
), .
, .
) | 2 O i O a Oe 1, i is odd, ak O j O n, j is eve.
Page 4: edges {.
, i ) | 1 O i O .
So mbt(P .
k r, .
) O 4.
(See Figure.
for the case a = 5, k = 2 and r = .
k is odd and r is even.
QkOe1 (Oe.
i (Oe.
i 1 Oe1 = AOe1 = C0 .
C1Oe1 , kOer 1 .
AkOer 2 , .
AkOe1 .
Ak .
i=kOer 1 Ai i=0 Ci (Oe.
aOe3 Oe1 Oe1 .
CkOe2 = D1 .
D2Oe1 , .
DaOe4 .
DaOe3 .
CkOe1 .
3 = i=1 i3 = .
, 2, .
, kOer, 1 , 2 , 3Oe1 }.
Let 1 = .
2 < r O k Oe 1 We can construct a matching book embedding of P .
k r, .
in a 4-page book as follows.
All the vertices are placed on the spine in the order i3 .
Oe1 3 ) , and all the edges can be placed in 4 pages so that the edges of the same page do not intersect each other and the edges induced subgraphs of each page are 1-regular.
Page 1: edges {.
jk, i jk .
| 1 O i O k, 0 O j O a Oe 3, j is eve.
and edges {.
, .
), .
, .
), .
, .
) | 1 O i O .
Oe .
k, i is odd, .
Oe .
k 1 O j O ak, j is even, ak 1 O m O n Oe 1, m is od.
Page 2: edges {.
Oe i Oe k, n Oe .
| 0 O i O k Oe .
, edges {.
, .
), .
, .
), .
, .
) | 1 O i O .
Oe .
k Oe 1, i is even, .
Oe .
k O j < ak, j is odd, ak 1 O m O n Oe 2, m is eve.
and edge .
, 1 ).
Page 3: edges {.
Oe i, n Oe .
, .
k Oe i, jk Oe i .
| 0 O i O k Oe 1, 1 O j O a Oe 2, j is eve.
, edges {(.
Oe .
k i, .
Oe .
k i .
| 1 O i O .
, edges {(.
, .
) | a Oe 1 O i O .
and edge (.
Oe .
, n ).
Page 4: edges {.
, i ) | 1 O i O .
Hence mbt(P .
k r, .
) O 4.
(See Figure.
for the case a = 3, k = 5 and r = .
0 O r O 2 Oe1 Oe1 Oe1 When r = 0, let i4 = {A1 .
AOe1 2 , .
AkOe1 .
Ak .
DaOe2 .
DaOe3 , .
D1 }.
We place all 2n ver0 tices on the spine in the ordering i4 .
Oe1 4 ) and assign the edges of P .
k r, .
to 4 pages as Matching book thickness of generalized Petersen graphs Zeling Shao et al.
Page 1: edges {.
jk, i jk .
| 1 O i O k, 0 O j O a Oe 2, j is eve.
, edge {.
Oe i 1, n Oe i 1 Oe .
| 0 O i O 2r , i is od.
and edges {.
, .
) | 1 O i O n Oe 1, i is od.
Page 2: edges {.
Oe i Oe k, n Oe .
| 2r O i O k Oe .
, edge .
, 1 ) and edges {.
, .
) | 1 O i O .
Oe .
k r, i is even and i 6= bk .
, where 2 O b O a Oe 1 and b is even.
Page 3: edges {.
Oe i, n Oe .
, .
jk, i jk .
| 0 O i O k Oe 1, 0 O j O a Oe 3, j is od.
and edges {(.
, .
k r .
), .
, .
) | 2 O i O a Oe 1, i is even, .
Oe .
k r 1 O j O n, j is eve.
Page 4: edges {.
, i ) | 1 O i O .
So P .
k r, .
can be matching embedded into 4 pages.
Oe1 Oe1 Oe1 When r = 2, let i5 = {A1 .
AOe1 2 , .
AkOe1 .
Ak , .
Oe.
k 1, .
Oe.
DaOe2 .
DaOe3 , .
D1 }.
Let the order of 2n vertices of P .
k r, .
on the spine be as i5 .
Oe1 5 ) , the edges of page 1, 2 and 4 are embedded in the same matching manner as when r = 0, but the edges {(.
Oe .
k i, .
Oe .
| 1 O i O .
are added in page 3 based on r = 0.
In summary, we can get a matching book embedding of P .
k r, .
in in a 4-page book.
Hence mbt(P .
k r, .
) O 4.
(See Figure.
for the case a = 3, k = 5 and r = 2 ) The result is obtained.
Conclusions In this paper, we study the matching book embedding of the generalized Petersen graph P .
, .
, and give different matching book embedding manners for the different parity of n and k.
Finally, we determine the matching book thickness of P .
, .
, that is, mbt(P .
, .
) = 3 when n is even and k is odd, and mbt(P .
, .
) = 4 in other cases.
Acknowledgement We sincerely thank the anonymous referee for useful comments to improve the paper.
This work was supported in part by Key Projects of Natural Science Research in College and universities of Hebei Province.
China (No.
ZD2020.
and the Natural Science Foundation of Hebei Province.
China (No.
A2021202.
Matching book thickness of generalized Petersen graphs Zeling Shao et al.
Figure 3.
The matching book embedding of P .
, .
P .
, .
P .
, .
and P .
, .
Matching book thickness of generalized Petersen graphs Zeling Shao et al.
References