Zeling Shao, Huiru Geng, Zhiguo Li^∗

Department of Mathematics, Hebei University of Technology, China

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

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.2022.10.1.11

1. Introduction

The book embedding of a graph was first introduced by Bernhart and Kainen [1]. The book embedding problem of a graph consists of arranging the vertices on the spine (a line) in order and placing the edges in the pages (the half planes with the spine as the common boundary), 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.

^∗Corresponding author.

said to be dispersable if it has a matching book embedding in \(\Delta(G)\) pages, i.e. \(mbt(G) = \Delta(G)\), where \(\Delta(G)\) is the maximum degree of G.

The book embedding of graphs have numerous applications(see [2-3]). Reference [4-7] 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 value. Bernhart and Kainen [1] proposed that complete bipartite graphs \(K_{n,n}\) \((n \ge 1)\), even cycles \(C_{2n}\) \((n \ge 2)\), binary n-cube Q(n) \((n \ge 0)\) and trees are dispersable and Overbay [8] gave detailed proof. For cartesian product graphs, Kainen [9] and Shao, Liu and Li [10] obtained that the matching book thickness of \(C_m \times C_n\) (m is even) and \(K_m \times C_n\) \((m, n \ge 3)\), respectively. In 2021, Kainen and Overbay showed that cubic planar bipartite graphs are dispersable (see [11]). For a Halin graph H, Shao, Geng, and Li [12] proved that mbt(H) = 4, if \(\Delta(H) = 3\) and \(mbt(H) = \Delta(H)\), if \(\Delta(H) \ge 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 [13]. The generalized Petersen graph P(n,k), \(n \geq 3\) and \(1 \leq k \leq n-1\), has vertex-set \(\{i,i' \mid i=1,2,\ldots,n\}\) and edge-set \(\{(i,i+k),(i',(i+1)'),(i,i') \mid i=1,2,\ldots,n\}\) ( mod n).

The generalized Petersen graph P(n,k) is always a 3-regular graph with 2n vertices and 3n edges, and P(5,2) is the well known Petersen graph, it can be matching embedded in a 4-page book (see Figure 1). From the definition of P(n,k), \(P(n,k) \cong P(n,n-k)\) for \(k < \frac{n}{2}\), thus we can assume \(1 \le k < \frac{n}{2}\).

Figure 1. P(5,2) (left) and the matching book embedding of P(5,2) (right).

In this paper, we obtain that the matching book thickness of a generalized Petersen graph P(n,k) as follows.

Main Theorem:

\[mbt(P(n,k)) = \begin{cases} 3, & n \text{ is even and } k \text{ is odd,} \\ 4, & \text{else.} \end{cases}\]

2. The Proof of Main Theorem

The proof will be completed by a sequence of lemmas.

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

Lemma 2.2. [8] For a regular graph G, G is dispersable only if G is bipartite.

Suppose \(X = \{x_1, \dots, x_i\}\) is an ordered vertex set with i vertices in P(n, k), we define \(X' := \{x'_1, \dots, x'_i\}\) and \(X^{-1} := \{x_i, \dots, x_1\}\), and call them paired ordering of X and reverse ordering of X, respectively.

Lemma 2.3. If P(n,k) is a generalized Petersen graph, n is even and \(1 \le k < \frac{n}{2}\), then

\[mbt(P(n,k)) = \begin{cases} 3, & k \text{ is odd}, \\ 4, & k \text{ is even}. \end{cases}\]

Proof. According to the parity of k, we need to consider two cases to prove the matching book thickness of P(n,k).

Case 1. k is odd.

Since \(\Delta(P(n,k))=3\), \(mbt(P(n,k))\geq 3\) by Lemma 2.1. Now we embed the vertices of P(n,k) along the spine according to the following ordering of \(1,n,3,n-2,\ldots,n-3,4,n-1,2,2',(n-1)',4',(n-3)'\ldots,(n-2)',3',n',1'\). All edges of P(n,k) can be placed on 3 pages in a matching manner as follows.

Page 1: edges \(\{(i,i+k),(i^{'},(i+1)^{'})\mid 1\leq i\leq n, i \text{ is odd}\}\) (mod n) .

Page 2: edges \(\{(i, i+k), (i', (i+1)') \mid 1 \le i \le n, i \text{ is even} \} \pmod{n}\).

Page 3: edges \(\{(i, i') \mid 1 \le i \le n\}\).

Hence \(mbt(P(n, k)) \le 3\). (See Figure 2(a) for the case k = 3 and n = 10).

Case 2. k is even.

In this case, P(n,k) is 3-regular but not bipartite because it contains at least one odd cycle. According to Lemma 2.2, P(n,k) is not dispersable, \(mbt(P(n,k)) \geq \Delta(P(n,k)) + 1 = 4\). Let d = gcd(n,k) be the greatest common denominator of n and k (here n and k are even, so d is even), \(\sigma_i\) is an ordered vertex set and \(\sigma_i = \{i, i+k, i+2k, \ldots, i+(\frac{n}{d}-1)k\}\) (mod n) \((1 \leq i \leq d)\), then \(V(P(n,k)) = \bigcup_{i=1}^{d} \sigma_i \sigma_i'\). We put all vertices on the spine in the ordering \(\sigma_1, \sigma_2^{-1}, \ldots, \sigma_{d-1}, \sigma_d^{-1}, (\sigma_d^{-1})', (\sigma_{d-1})', \ldots, (\sigma_2^{-1})', (\sigma_1)'\) and assign the edges of P(n,k) to 4 pages as follows.

Page 1: edges \(\{(n-i+ak, n-i+(a+1)k) \mid 1 \le i \le d, 0 \le a \le \frac{n}{d}-2, a \text{ is even}\} \pmod{n}\) and edges \(\{(i^{'}, (i+1)^{'}) \mid 1 \le i \le n, i \text{ is odd}\}.\)

Page 2: edges \(\{(n-i+ak, n-i+(a+1)k) \mid 1 \le i \le d, 0 \le a \le \frac{n}{d}-2, a \text{ is odd}\} \pmod{n}\) and edges \(\{((d+jk)', (d+jk+1)') \mid 0 \le j \le b\} \pmod{n}\), where \(b = min\{c \in Z^+ \mid d+ck \equiv n-k \pmod{n}\}\).

Page 3: edges \(\{(n-i-k,n-i) \mid 1 \leq i \leq d\}\), edges \(\{((i+jk)',(i+jk+1)') \mid 1 \leq i < d,i \text{ is even}, 0 \leq j \leq \frac{n}{d}-1\} \pmod{n}\) and edges \(\{((d+jk)',(d+jk+1)') \mid b+1 \leq j \leq \frac{n}{d}-1\} \pmod{n}\), where \(b=\min\{c \in Z^+ \mid d+ck \equiv n-k \pmod{n}\}\).

Page 4: edges \(\{(i, i') | 1 \le i \le n\}\).

Therefore we get a matching book embedding of P(n,k) in a 4-page book, \(mbt(P(n,k)) \le 4\). (See Figure 2(b) for the case k=4 and n=10).

The result is established.

Figure 2. The matching book embedding of P(10, 3) and P(10, 4).

Lemma 2.4. If P(n,k) is a generalized Petersen graph, n is odd and \(1 \le k < \frac{n}{2}\), then \(mbt(P(n,k)) = \Delta(P(n,k)) + 1 = 4\).

Proof. Since n is odd, P(n,k) contains an odd cycle \(C_n\) according to its definition, it is not bipartite, and then P(n,k) is 3-regular, so it is not dispersible by Lemma 2.2, \(mbt(P(n,k)) \geq \Delta(P(n,k)) + 1 = 4\).

Let n = ak + r \((a \ge 2, 0 \le r < k)\), \(A_i\), \(B_i\), \(C_i\) and \(D_i\) be ordered vertex set, \(A_i = \{i, i+n-k\}\) \((1 \le i \le k)\), \(B_i = \{ik, ik-1, \ldots, ik-(k-1)\}\) \((2 \le i \le a)\), \(C_i = \{ak-i, ak-i-k\}\) \((0 \le i \le k-1)\), \(D_i = \{ik+1, ik+2, \ldots, ik+k\}\) \((1 \le i \le a)\). According to the parity of a, we need to consider two cases to prove that \(mbt(P(ak+r,k)) \le 4\) as follows.

Case 1. a is even.

It is easy to know that r is odd because n is odd and a is even. Assume \(\alpha_1 = \prod_{i=k-r+1}^k A_i^{(-1)^{i+1}} = A_{k-r+1}^{(-1)^{k-r+2}}, A_{k-r+2}^{(-1)^{k-r+3}}, \ldots, A_k^{(-1)^{k+1}}; \alpha_2 = \prod_{i=2}^a B_i^{(-1)^{i+1}} = B_2^{-1}, B_3, \ldots, B_{a-1}, B_a^{-1}; \varphi_1 = \{1, 2, \ldots, k-r, \alpha_1, \alpha_2^{-1}\}\). Now we can construct a matching book embedding of P(ak+r,k) in a 4-page book as follows. Put all 2n vertices on the spine in the ordering \(\varphi_1(\varphi_1^{-1})'\) and assign all edges to 4 pages.

Page 1: edges \(\{(i+jk, i+jk+k) \mid 1 \le i \le k, 0 \le j \le a-1, j \text{ is even} \}\) and edges \(\{(i', (i+1)'), (j', (j+1)') \mid 1 \le i \le 2k, i \text{ is odd}, 2k \le j \le ak, j \text{ is even and } j \ne bk \}\), where \(1 \le b \le a\) and b is even.

Page 2: edges \(\{(n-i-k,n-i) \mid 0 \le i \le r-1\}\) and edges \(\{(i^{'},(i+1)^{'}),(j^{'},(j+1)^{'}) \mid 1 \le i \le 2k-1, i \text{ is even}, 2k \le j \le n, j \text{ is odd}\}\) (mod n).

Page 3: edges \(\{(k-i,n-i),(jk-i,jk-i+k) \mid 0 \le i \le k-1, 1 \le j \le a-1, j \text{ is even} \}\) and edges \(\{((ak+i)',(ak+i+1)'),((jk)',(jk+1)') \mid 1 \le i \le r, i \text{ is even}, 2 \le j \le a, j \text{ is even} \}\). Page 4: edges \(\{(i,i') \mid 1 \le i \le n\}\).

Hence \(mbt(P(ak+r,k)) \le 4\). (See Figure.3(a) for the case a=2, k=4 and r=3).

Case 2. a is odd.

In this case, we prove \(mbt(P(ak+r,k)) \leq 4\) from the following two situations.

(1) k is even and r is odd.

We denote \(\beta_1 = \prod_{i=k-r+1}^k A_i^{(-1)^{i+1}} = A_{k-r+1}^{-1}, A_{k-r+2}, \dots, A_{k-1}, A_k^{-1}; \beta_2 = \prod_{i=0}^{k-1} C_i^{(-1)^{i+1}} = C_0^{-1}, C_1, \dots, C_{k-2}^{-1}, C_{k-1}; \beta_3 = \prod_{i=1}^{a-3} D_i^{(-1)^{i+1}} = D_1, D_2^{-1}, \dots, D_{a-4}, D_{a-3}^{-1}; \varphi_2 = \{1, 2, \dots, k-r, \beta_1, \beta_2, \beta_3^{-1}\}.\) All 2n vertices of P(ak+r, k) are assigned on the spine by the ordering of \(\varphi_2(\varphi_2^{-1})'\) and all edges of P(ak+r, k) can be matching embedded in a 4-page book as follows.

Page 1: edges \(\{(i+jk, i+jk+k) \mid 1 \le i \le k, 0 \le j \le a-3, j \text{ is even}\}\) and edges \(\{(i^{'}, (i+1)^{'}), (j^{'}, (j+1)^{'}) \mid 1 \le i \le 3k, i \text{ is odd}, \ 3k+1 \le j \le ak-1, j \text{ is even and } j \ne bk\}\), where 3 < b < a, b is odd.

Page 2: edges \(\{(n-i-k,n-i) \mid 0 \le i \le k-1\}\) and edges \(\{(i^{'},(i+1)^{'}),(j^{'},(j+1)^{'}) \mid 1 \le i \le 3k-1, i \text{ is even}, 3k \le j \le n, j \text{ is odd}\}\) (mod n).

Page 3: edges \(\{(k-i,n-i),(jk-i,jk-i+k)\mid 0\leq i\leq k-1,1\leq j\leq a-2,j \text{ is even}\}\), edges \(\{((a-2)k+i,(a-2)k+i+k)\mid 1\leq i\leq r\}\) and edges \(\{((ik)',(ik+1)'),(j',(j+1)')\mid 2\leq i\leq a-1,i \text{ is odd}, ak\leq j\leq n,j \text{ is even}\}\).

Page 4: edges \(\{(i, i') | 1 \le i \le n\}\).

So \(mbt(P(ak + r, k)) \le 4\). (See Figure.3(b) for the case a = 5, k = 2 and r = 1).

(2) k is odd and r is even.

Let \[\gamma_1 = \prod_{i=k-r+1}^k A_i^{(-1)^{i+1}} = A_{k-r+1}^{-1}, A_{k-r+2}, \dots, A_{k-1}^{-1}, A_k; \ \gamma_2 = \prod_{i=0}^{k-1} C_i^{(-1)^i} = C_0, C_1^{-1}, \dots, C_{k-2}^{-1}, C_{k-1}; \ \gamma_3 = \prod_{i=1}^{a-3} D_i^{(-1)^{i+1}} = D_1, D_2^{-1}, \dots, D_{a-4}, D_{a-3}^{-1}; \ \varphi_3 = \{1, 2, \dots, k-r, \gamma_1, \gamma_2, \gamma_3^{-1}\}.\]

(i) \[2 < r \le k - 1\]

We can construct a matching book embedding of P(ak+r,k) in a 4-page book as follows. All the vertices are placed on the spine in the order \(\varphi_3(\varphi_3^{-1})'\), 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 \(\{(i+jk,i+jk+k) \mid 1 \le i \le k, 0 \le j \le a-3, j \text{ is even}\}\) and edges \(\{(i',(i+1)'),(j',(j+1)'),(m',(m+1)') \mid 1 \le i \le (a-1)k, i \text{ is odd},(a-1)k+1 \le j \le ak, j \text{ is even}, ak+1 \le m \le n-1, m \text{ is odd}\}.\)

Page 2: edges \(\{(n-i-k,n-i) \mid 0 \le i \le k-1\}\), edges \(\{(i^{'},(i+1)^{'}),(j^{'},(j+1)^{'}),(m^{'},(m+1)^{'}) \mid 1 \le i \le (a-1)k-1, i \text{ is even}, (a-1)k \le j < ak, j \text{ is odd}, ak+1 \le m \le n-2, m \text{ is even}\}\) (mod n) and edge \((n^{'},1^{'})\).

Page 3: edges \(\{(k-i,n-i),(jk-i,jk-i+k) \mid 0 \le i \le k-1,1 \le j \le a-2,j \text{ is even}\}\), edges \(\{((a-2)k+i,(a-2)k+i+k) \mid 1 \le i \le r\}\), edges \(\{((ik)',(ik+1)') \mid a-1 \le i \le a\}\) and edge ((n-1)',n').

Page 4: edges \(\{(i, i') \mid 1 \le i \le n\}\).

Hence \(mbt(P(ak+r,k)) \le 4\). (See Figure.3(c) for the case a=3, k=5 and r=4).

(ii) \[0 \le r \le 2\]

When r=0, let \(\varphi_4=\{A_1,A_2^{-1},\ldots,A_{k-1}^{-1},A_k,D_{a-2}^{-1},D_{a-3},\ldots,D_1^{-1}\}\). We place all 2n vertices on the spine in the ordering \(\varphi_4(\varphi_4^{-1})'\) and assign the edges of P(ak+r,k) to 4 pages as

follows.

Page 1: edges \(\{(i+jk, i+jk+k) \mid 1 \le i \le k, 0 \le j \le a-2, j \text{ is even}\}\), edge \(\{(n-i+1, n-i+1-k) \mid 0 \le i \le \frac{r}{2}, i \text{ is odd}\}\) and edges \(\{(i', (i+1)') \mid 1 \le i \le n-1, i \text{ is odd}\}\).

Page 2: edges \(\{(n-i-k,n-i) \mid \frac{r}{2} \leq i \leq k-1\}\), edge (n',1') and edges \(\{(i',(i+1)') \mid 1 \leq i \leq (a-1)k+r, i \text{ is even and } i \neq bk+r\}\), where \(2 \leq b \leq a-1\) and b is even.

Page 3: edges \(\{(k-i, n-i), (i+jk, i+jk+k) \mid 0 \le i \le k-1, 0 \le j \le a-3, j \text{ is odd}\}\) and edges \(\{((ik+r)', (ik+r+1)'), (j', (j+1)') \mid 2 \le i \le a-1, i \text{ is even}, (a-1)k+r+1 \le j \le n, j \text{ is even}\}.\)

Page 4: edges \(\{(i, i') \mid 1 \le i \le n\}\).

So P(ak + r, k) can be matching embedded into 4 pages.

When r=2, let \(\varphi_5=\{A_1,A_2^{-1},\ldots,A_{k-1}^{-1},A_k,(a-1)k+1,(a-1)k+2,D_{a-2}^{-1},D_{a-3},\ldots,D_1^{-1}\}\). Let the order of 2n vertices of P(ak+r,k) on the spine be as \(\varphi_5(\varphi_5^{-1})'\), the edges of page 1, 2 and 4 are embedded in the same matching manner as when r=0, but the edges \(\{((a-2)k+i,(a-1)k+i)\mid 1\leq i\leq 2\}\) are added in page 3 based on r=0.

In summary, we can get a matching book embedding of P(ak+r,k) in in a 4-page book. Hence \(mbt(P(ak+r,k)) \le 4\). (See Figure.3(d) for the case a=3, k=5 and r=2)

The result is obtained.

3. Conclusions

In this paper, we study the matching book embedding of the generalized Petersen graph P(n,k), and give different matching book embedding manners for the different parity of n and k. Finally, we determine the matching book thickness of P(n,k), that is, mbt(P(n,k))=3 when n is even and k is odd, and mbt(P(n,k))=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.ZD2020130) and the Natural Science Foundation of Hebei Province, China (No. A2021202013).

Figure 3. The matching book embedding of P(11, 4), P(11, 2), P(19, 5) and P(17, 5).

References

• [1] F. Bernhart and P.C. Kainen, The book thickness of a graph, J. Combin. Theory Ser. 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 J. Algebraic Discrete Method 8(1) (1987), 33–58.
• [3] H.A. Akitaya, E.D. Demaine, and A. Hesterberg, Upward partitioned book embeddings, Lecture Notes in Computer Science 10692 (2017), 210–223.
• [4] B. Zhao, W. Xiong, and Y.Z. Tian, Embedding generalized Petersen graph in books, Chinese Ann. Math. Ser. B 37(3) (2016), 385–394.
• [5] Z.L. Shao, C.Y. Qi, and Z.G. Li, Book embedding of graph bundles over a cycle with claw as a fibre, Utilitas Mathematica 116 (2020), 33–44.
• [6] J. Yang, Z.L. Shao, and Z.G. Li, Embedding cartesian product of some graphs in books, Commun. Math. Res 34(03) (2018), 253–260.
• [7] M. Yannakakis, Planar graphs that need four pages, J. Combin. Theory Ser. B 145 (2020), 241–263.
• [8] S. Overbay, Generalized book embeddings, Fort Collins: Colorado State University Ph.D Thesis, 1998.
• [9] P.C. Kainen, Complexity of products of even cycles, Bull.Inst.combin.Application 62 (2011), 95–102.
• [10] 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.
• [11] P.C. Kainen, and S. Overbay, Cubic planar bipartite graphs are dispersable, arXiv:2107.04728.
• [12] Z.L. Shao, H.R. Geng, and Z.G. Li, Matching book thickness of Halin graphs, arXiv:2008.13331.
• [13] M. E. Watkins, A theorem on tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory 6 (1969), 152–164.