Zeling Shao, Yanling Hu, Huiru Geng, Zhiguo Li^∗

Department of Mathematics, Hebei University of Technology, China

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

The book embedding of a graph G is to arrange the set of points of the graph on a line (spine) and embed the edges on the half-plane bounded by the spine so that the edges in the same page do not intersect with each other. If the maximum degree of vertices in each page is 1, the book embedding is matching book embedding. The matching book thickness of G is the minimum number n that G can be matching book embedded in n-page. In this paper, the matching book thickness of pseudo-Halin graphs is determined.

Keywords: book embedding, matching book embedding, matching book thickness, pseudo-Halin graph Mathematics Subject Classification : 05C10; 68R10

DOI: 10.5614/ejgta.2023.11.1.23

1. Introduction

The concept of book embedding was first proposed by Bernhart and Kainen [1]. A book consists of a spine and several pages. The spine can be seen as a line and the pages are half-planes with the spine as a common boundary. The book embedding of a graph consists of two parts, one is to arrange the vertices on the spine in order, and the other is to embed the edges into the pages so that the edges in the same page do not cross. The book thickness of a graph G is the least number n that G has an n-book embedding.

Received: 17 September 2022, Revised: 26 February 2023, Accepted: 4 March 2023.

^∗ corresponding author

A book embedding of a graph G is matching if the degree of vertices on each page is at most one. The matching book thickness of a graph G is the least number n that G can be matching book embedded in n pages, which we denoted by mbt(G) [2]. A graph G is dispersable if mbt(G) = ∆(G), where ∆(G) is the maximum degree of G. A graph G is nearly dispersable if mbt(G) = ∆(G) + 1, see [3].

Book embeddings have been extensively studied for various families of graphs [3-8]. Meanwhile, the question of determining a graph is dispersable or not has aroused widespread concern for its connection to edge coloring. Complete bipartite graphs Kn,n (n ≥ 1), even cycles C2ⁿ (n ≥ 2), binary n-cube Q(n) (n ≥ 0) and trees are dispersable [1]. Kainen [2] shows that mbt(Cp✷Cq) is 4, when p and q are both even and mbt(Cp✷Cq) is 5, when p is even, q is odd. Kainen also gives some dispersability of circulant graphs [9] and bipartite cubic planar graphs are dispersable [10]. Joslin [11] shows that mbt(Cm✷Cn) is 5, when m is 3 or 5. In [3], it is proved that any regular dispersable graph G is bipartite and the matching book thickness of the complete graph Kⁿ is n. Recently, the first author et al. have obtained the matching book thickness of generalized Petersen graphs [12],bipartite cubic planar graphs [13] and, cartesian product of complete graphs and cycles [14].

A 2-connected planar graph G with minimum degree at least 3 is a pseudo-Halin graph [15] if deleting the edges on the boundary of a single face f⁰ yields a tree. It is a Halin graph if the vertices of f⁰ all have degree 3 in G. The face f⁰ is the exterior face; the others are interior faces. Vertices of f⁰ are exterior vertices; the others are interior vertices. Vertices of f⁰ with degree 3 in G are regular vertices; the others are irregular vertices. Let R(f0) and IR(f0) denote the sets of regular and irregular vertices in f0, respectively. In particular, a pseudo-Halin graph with ∆(G) = 3 is a cubic Halin graph, see Figure 1 for a Halin graph and a pseudo-Halin graph with ∆(G) = 4, respectively.

Figure 1 (Left) An example of a Halin graph. (Right) An example of a pseudo-Halin graph.

In this paper, we compute the matching book thickness of a pseudo-Halin graph G as follows.

Main theorem:

\[mbt(G) = \begin{cases} 4, & \Delta(G) = 3, \\ \Delta(G), & \Delta(G) \ge 4. \end{cases}\]

2. The proof of the main theorem

The proof will be completed by a sequence of results. We recall that the chromatic index of a graph G is denoted by \(\chi'(G)\).

Remark 2.1 (3, pg. 87). For any simple graph \(G, \Delta(G) \leq \chi'(G) \leq mbt(G)\).

Let G be a simple graph with p vertices. Suppose that G has an n-book embedding. All vertices of G occur in some specified order \(v_1, \dots, v_p\) from "top" to "bottom" along the spine and this sequence is called the printing cycle of the embedding [1]. Similarly, we can define a printing cycle for a matching book embedding of a graph. Sometimes it is convenient to understand the matching book embedding from another point of view as for book embedding of graphs in [16], that is, to embed the graph G so that its vertices lie on a circle and its edges are chords of the circle; to assign the chords to layers so that chords on the same layer do not cross and meet each other. By the rotations of the vertices on the circle, it is easy to get the following result which is a natural generalization of Remark 2.2 and Lemma 2.1 of [1].

Remark 2.2 (3, pg. 88). If a regular graph G is dispersable, then G is bipartite.

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

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

Lemma 2.2. Let \(W_m\) be a wheel graph with m vertices \((m \ge 4)\),

\[mbt(W_m) = \begin{cases} 4, & m = 4, \\ \Delta(W_m), & m \ge 5. \end{cases}\]

Proof. If m = 4, then \(W_4\) is \(K_4\). Hence \(mbt(W_4) = 4\).

If \(m \geq 5\), it follows by Remark 2.1 that \(mbt(W_m) \geq \Delta(W_m)\). Assume u is the center vertex of \(W_m\) whose has neighbours on \(f_0\), in counterclockwise order, denoted by \(v_1, v_2, ..., v_{m-1}\). We embed the vertices of \(W_m\) along the spine according to the following ordering of \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)..., \(v_1, u, v_{\lfloor \frac{m-1}{2} \rfloor + 1}, v_{\lfloor \frac{m-1}{2} \rfloor + 2}, \dots, v_{m-1}\). We assign the edges of \(W_m\) to the m-1 pages as follows.

Page 1: the edges \(\{(uv_1), (v_2v_3)\};\)

Page i: the edges \(\{(uv_i), (v_{i+1}v_{i+2})\};\)

Page m-3: the edges \(\{(uv_{m-3}), (v_{m-2}v_{m-1})\};\)

Page m-2: the edges \(\{(uv_{m-2}), (v_{m-1}v_1)\};\)

Page m-1: the edges \(\{(uv_{m-1}), (v_1v_2)\}.\)

Therefore, \(mbt(W_m) \leq m-1 = \Delta(W_m)\). The result is established, see Figure 2 for the case m = 6 and m = 7.

The matching book embeddings of pseudo-Halin graphs | Zeling Shao et al.

Figure 2 (Left) The matching book embedding of W6. (Right) The matching book embedding of W7.

Lemma 2.3. If H is a cubic Halin graph, then mbt(H) = 4.

Proof. It is easy to see that Halin graph H contains at least one 3-cycle. By Remark 2.2, we have H is not dispersable. Hence mbt(H) ≥ ∆(H) + 1 = 4.

Next, we show that mbt(G) ≤ 4 by induction on the number n of interior vertices. If n = 1, then H = K4. Thus, mbt(H) = ∆(K4) = 4. Assume that mbt(H) ≤ 4 holds for n = 1, 2, · · · , m. We need to show that mbt(G) ≤ 4 for any cubic Halin graph H with m + 1 interior vertices. By the definition of Halin graph, H contains at least one interior vertex which is adjacent to at least two leaves. Assume w is an interior vertex of H whose has neighbours on f0, in counterclockwise order, denoted by v1, v2, see Figure 3 (a). Because deg(w) = 3, w has only one other neighbour which is denoted by u. Let x be the adjacent vertex on f⁰ before v¹ and y be the adjacent vertex on f⁰ behind v² (x ̸= y).

Consider the graph H′ obtained from H by contracting w, v1, v² to a single vertex w ′ , see Figure 3 (b). H′ is still a cubic Halin graph with m interior vertices. By induction, mbt(H′ ) ≤ 4. In other words, the graph H′ has a 4-page matching book embedding. We put the vertices of H′ along the spine according to such a matching book embedding. By Lemma 2.1, it suffices to consider one vertex ordering of H′ on the spine as ..., x, ..., w′ , ..., y′ , ..., see Figure 3 (d). Now we construct a matching book embedding of H from that of H′ .

First, we replace the vertex w ′ with 3 vertices w, v1, v² on the spine in the ordering of v1, w, v2. Without loss of generality, assume the edges w ′u, w′x, w′ y are assigned to the page 1, 2, 3, respectively, in the matching book embedding of H′ . Now we assign the edges wu, v1x, v2y to the page 1, 2, 3, respectively, and the edges wv2, wv1, v1v² to the page 2, 3, 4, respectively, see Figure 3 (c); Other edges of H are assigned to the same page as that of H′ . It is easy to see that we get a matching book embedding of H in 4-book. Hence mbt(H) ≤ 4.

The result is established.

Lemma 2.4. If G is a pseudo-Halin graph with ∆(G) = 3, then mbt(G) = 4.

Proof. Since a pseudo-Halin graph with ∆(G) = 3 is a cubic Halin graph, it follows from Lemma 2.3 that mbt(G) = 4.

Lemma 2.5. [15] If G is a pseudo-Halin graph (G ̸= Wp) with exterior face f⁰ and P = u1u2...u^k is the longest path in G − E(f0), w ∈ {u2, uk−1}, let N(w) be the set of neighbours of the vertex w, then one of the following results holds:

(1) The vertex w is an interior vertex with N(w) ⊆ V (f0), |N(w) ∩ IR(f0)| = 1. Let N(w) = {y, v1, v2, ..., vm} (m ≥ 2); xv1, vivi+1, vmy ∈ E(f0), y ∈ IR(f0), x ̸= v² and y ̸= vm−1, i = 1, 2, ..., m − 1, then

The matching book embeddings of pseudo-Halin graphs Zeling Shao et al.

Figure 3 (a) The cubic Halin graph H. (b) The reduced graph H'. (c) The matching book embedding of H. (d)The matching book embedding of H'.

\(G_1^1 := G - \{w, v_i | i = 1, 2, ..., k\} + \{xy\}\) and \(G_1^2 := G - \{v_i, v_{i+1}, ..., v_j\} + \{v_{i-1}v_{j+1}\}\) \((2 \le i < j \le m-1)\) are also pseudo-Halin graphs.

(2) The vertex w is an interior vertex with \(|N(w) \cap (V(G) \setminus V(f_0))| = 1\), \(|N(w) \cap R(f_0)| = 1\)d(w) - 1. Let \(N(w) = \{u, v_1, ..., v_m\}\), u being interior vertex, \(v_i \in R(f_0)\) (i = 1, 2, ..., m), \(xv_1, v_iv_{i+1}, v_my \in E(f_0)\) \((i = 1, 2, ..., m-1), x \neq v_2 \text{ and } y \neq v_{m-1}, then\)

\(G_2^1:=G-\{v_1,v_2,...,v_m\}+\{xw,yw\}\) and \(G_2^2:=G-\{v_i,v_{i+1},...,v_j\}+\{v_{i-1}v_{j+1}\}\;(2\leq i< j\leq m,\;m\geq 3)\;\text{are also pseudo-Halin}\)graphs.

Lemma 2.6. If G is a pseudo-Halin graph with \(\Delta(G) > 4\), then \(mbt(G) = \Delta(G)\).

Proof. According to Remark 2.1, we have \(mbt(G) \geq \Delta(G)\).

Next we show that \(mbt(G) < \Delta(G)\) by induction on the number n of interior vertices. If n=1, then G is a wheel graph. It follows from Lemma 2.2 that \(mbt(G) < \Delta(G)\). Assume that \(mbt(G) \leq \Delta(G)\) holds for \(n = 1, 2, \dots, m\). We need to show that \(mbt(G) \leq \Delta(G)\) for any pseudo-Halin graph G with m+1 interior vertices. Let \(P=u_1u_2...u_p\) is the longest path in \(G - E(f_0), w \in \{u_2, u_{p-1}\}\). In order to complete the proof, we need to consider the following two cases:

Case 1. The vertex w is an interior vertex with \(N(w) \subseteq V(f_0)\), \(|N(w) \cap IR(f_0)| = 1\).

Assume that the neighbours of w on \(f_0\) are \(v_1, v_2, ..., v_k, y\) \((k \ge 2)\) in counterclockwise order. Obviously, \(xv_1, v_i v_{i+1}, v_k y \in E(f_0), y \in IR(f_0), x \neq v_2 \text{ and } y \neq v_{k-1} \ (i = 1, 2, ..., k-1).\)Let x be the adjacent vertex on \(f_0\) before \(v_1\), y' be the adjacent vertex on \(f_0\) behind y and \(z_t\) (t=1, 2, ..., j) be the adjacent interior vertex of y, see Figure 4 (a) for the case k = 4, j = 1.

Consider the graph G' obtained from G by contracting \(w, v_1, v_2, ..., v_k, y\) to a single vertex w', see Figure 4 (b) for the case k = 4, j = 1. By Lemma 2.6, G' is still a pseudo-Halin graph with m interior vertices. We need to consider two situations:

Situation 1: \(4 \le \Delta(G') \le \Delta(G)\).

Figure 4 (a)The pseudo-Halin graph G. (b)The reduced graph G'. (c)The matching book embedding of G. (d)The matching book embedding of G'.

By induction, \(mbt(G') \leq \Delta(G')\). In other words, the graph G' has a \(\Delta(G')\)-page matching book embedding. We put the vertices of G' along the spine according to such a matching book embedding. By Lemma 2.1, it suffices to consider one vertex ordering of G' on the spine as \(\cdots, x, ..., w', ..., y', ...\), see Figure 4 (d). Now we construct a matching book embedding of G from that of G'. First, we replace the vertex w' with k+2 vertices \(w, v_1, v_2, ..., v_k, y\) on the spine in the ordering of \(v_{\lceil \frac{k+1}{2} \rceil}, v_{\lceil \frac{k+1}{2} \rceil - 1}, v_{\lceil \frac{k+1}{2} \rceil - 2}, ..., v_1, w, v_{\lceil \frac{k+1}{2} \rceil + 1}, ..., v_k, y\). Without loss of generality, assume the edges \(w'x, w'y', w'z_1, ..., w'z_j\) are assigned to the page 1, 2, ..., j+2, respectively, in the matching book embedding of G'. Next, we consider the matching book embedding of G from the following two cases.

(I) deg(w) = k + 1 = \Delta(G)

We assign the edges of G to the \Delta(G) pages as follows.

(a) \ deg(w) = deg(y), i.e. k = j + 2

Page 1: the edges \{(wy), (xv_1)\};

Page 2: the edges \{(yy'), (wv_k), (v_1v_2)\};

Page 3: the edges \{(yz_1), (wv_1), (v_2v_3)\};

Page 4: the edges \{(yz_2), (wv_2), (v_3v_4)\};

.....

Page i: the edges \{(yz_{i-2}), (wv_{i-2}), (v_{i-1}v_i)\};

.....

Page j + 2: the edges \{(yz_j), (wv_j), (v_{j+1}v_{j+2})\};

Page k + 1: the edges \{(wv_{k-1}), (v_ky)\};

Other edges of G are assigned to the same pages as that of G′ . It is immediate that we get a matching book embedding of G in ∆(G)-book. Hence mbt(G) ≤ ∆(G).

(b) deg(w) > deg(y), i.e. k > j + 2
Page 1: the edges {(wy),(xv1)};
Page 2: the edges {(yy′
                       ),(wvk),(v1v2)};
Page 3: the edges {(yz1),(wv1),(v2v3)};
Page 4: the edges {(yz2),(wv2),(v3v4)};
· · · · · ·
Page i: the edges {(yzi−2),(wvi−2),(vi−1vi)};
· · · · · ·
Page j + 2: the edges {(yzj ),(wvj ),(vj+1vj+2)};
Page j + 3: the edges {(wvj+1),(vj+2vj+3)};
· · · · · ·
Page k: the edges {(wvk−2),(vk−1vk)};
Page k + 1: the edges {(wvk−1),(vky)};

Other edges of G are assigned to the same pages as that of G′ . It is easily seen that we get a matching book embedding of G in ∆(G)-book. Hence mbt(G) ≤ ∆(G), see Figure 4 (c) for the case k = 4, j = 1.

(II) deg(w) = k + 1 < ∆(G)
  (a) deg(w) = 3

We assign the edges of G to the j + 3 pages as follows. Other edges of G are assigned to the same pages as that of G′ . It is easy to see that we get a matching book embedding of G in ∆(G)-book, see Figure 5 for the case j = 1.

Page 1: the edges {(wy),(xv1)};
Page 2: the edges {(yy′
                        ),(wv2)};
Page 3: the edges {(yz1),(v1v2)};
Page 4: the edges {(yz2)};
· · · · · ·
Page i: the edges {(yzi−2)};
· · · · · ·
Page j + 2: the edges {(yzj )};
Page j + 3: the edges {(wv1),(v2y)};
  (b) deg(w) ≥ 4 and ∆(G) = deg(y)

If ∆(G) = deg(y) = j + 3, we assign the edges of G to the j + 3 pages as follows. Other edges of G are assigned to the same pages as that of G′ . It is obvious that we get a matching book embedding of G in ∆(G)-book.

Page 1: the edges {(wy),(xv1)};
Page 2: the edges {(yy′
                        ),(wvk),(v1v2)};
Page 3: the edges {(yz1),(wv1),(v2v3)};
Page 4: the edges {(yz2),(wv2),(v3v4)};
· · · · · ·
Page i: the edges {(yzi−2),(wvi−2),(vi−1vi)};
· · · · · ·

The matching book embeddings of pseudo-Halin graphs | Zeling Shao et al.

Figure 5 (a)The pseudo-Halin graph G. (b)The reduced graph G ′ . (c)The matching book embedding of G. (d)The matching book embedding of G′ .

Page k: the edges {(yzk−2),(wvk−2),(vk−1vk)};
Page k + 1: the edges {(yzk−1)};
· · · · · ·
Page j + 2: the edges {(yzj )};
Page j + 3: the edges {(vky),(wvk−1)};
  (c) deg(w) ≥ 4 and ∆(G) ̸= deg(y).

It is easy to verify that ∆(G) = ∆(G′ ). We assign the edges of G to the max{j + 3, k + 1} pages. We can construct a ∆(G′ )-page matching book embedding of G from that of G′ in the same way as the case (I) or the case (II)(b). Other edges of G are assigned to the same pages as that of G′ . Hence mbt(G) ≤ ∆(G′ ) = ∆(G).

Situation 2: ∆(G′ ) = 3.

By Lemma 2.2, mbt(G′ ) = 4. In a similar way as Situation 1 we can construct a matching book embedding of G in a ∆(G)-page book. Hence mbt(G) ≤ ∆(G).

Case 2. The vertex w is an interior vertex with |N(w)∩(V (G)\V (f0))| = 1, |N(w)∩R(f0)| = d(w) − 1.

Assume that the neighbours of w on f⁰ are v1, v2, ..., v^k (k ≥ 2) in counterclockwise order. Obviously, xv1, vivi+1, vky ∈ E(f0), x ̸= v² and y ̸= vk−¹ (i = 1, 2, ..., k − 1). Let x be the adjacent vertex on f⁰ before v1, y be the adjacent vertex on f⁰ behind v^k and u be the interior adjacent vertex of w, see Figure 6 (a).

Consider the graph G′ obtained from G by contracting w, v1, v2, ..., v^k to a single vertex w ′ , see Figure 6 (b). By Lemma 2.5, G′ is still a pseudo-Halin graph with m interior vertices. We need to consider two situations:

Situation 1: 4 ≤ ∆(G′ ) ≤ ∆(G).

The matching book embeddings of pseudo-Halin graphs | Zeling Shao et al.

Figure 6 (a) The pseudo-Halin graph G. (b) The reduced graph G'. (c) The matching book embedding of G. (d) The matching book embedding of G'.

By induction, \(mbt(G') \leq \Delta(G')\). That is to say, the graph G' has a \(\Delta(G')\)-page matching book embedding. We put the vertices of G' along the spine according to such a matching book embedding. By Lemma 2.1, it is sufficient to consider one vertex ordering of G' on the spine as ..., x, ..., w', ..., y, ..., see Figure 6 (d). Now we construct a matching book embedding of G from that of G'. First, we replace the vertex w' with k+1 vertices \(w, v_1, v_2, ..., v_k\) on the spine in the ordering of \(v_{\lceil \frac{k}{2} \rceil}, v_{\lceil \frac{k}{2} \rceil - 1}, v_{\lceil \frac{k}{2} \rceil - 2}, ..., v_1, w, v_{\lceil \frac{k+1}{2} \rceil + 1}, ..., v_k\). Without loss of generality, assume the edges w'u, w'x, w'y are assigned to the page 1, 2, 3, respectively, in the matching book embedding of G'. Next we consider the matching book embedding of G from the following two cases.

(I) deg(w) = k + 1 = \Delta(G)

We assign the edges of G to the \Delta(G) pages as follows.

Page 1: the edges \{(wu), (v_1v_2)\};

Page 2: the edges \{(wv_k), (xv_1)\};

Page 3: the edges \{(wv_{k-1})(v_ky)\};

Page 4: the edges \{(wv_1), (v_2v_3)\};

Page 5: the edges \{(wv_2), (v_3v_4)\};

......

Page i: the edges \{(yz_{i-3}), (v_{i-2}v_{i-1})\};

.....

Page k + 1: the edges \(\{(wv_{k-2}), (v_{k-1}v_k)\}\);

Other edges of G are assigned to the same pages as that of G'. It is easy to check that we get a matching book embedding of G in \(\Delta(G)\)-book. Hence \(mbt(G) \leq \Delta(G)\), see Figure 6 (c) for the case k=6.

(II) \[deg(w) = k + 1 < \Delta(G)\]

If ∆(G) > deg(w), then ∆(G) = ∆(G′ ), i.e. deg(w) < ∆(G′ ). We can construct a ∆(G′ ) page matching book embedding of G from that of G′ in the same way as the case (I). Hence mbt(G) ≤ ∆(G′ ) = ∆(G).

Situation 2: ∆(G′ ) = 3.

It is clear that ∆(G) = ∆(w). In a similar way as Situation 1(I) we can construct a matching book embedding of G in a ∆(G)-page book. Hence mbt(G) ≤ ∆(G).

This completes the proof.

3. Conclusions

In this paper, we study the matching book embedding of a pseudo-Halin graph G and determine its matching book thickness. Specifically, we get the pseudo-Halin graph G is nearly dispersable when ∆(G) = 3 and dispersable otherwise.

Acknowledgement

We sincerely thank the anonymous referee for useful comments to improve the paper. This work was supported in part 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, J. Combin. Theory Ser. B 27 (1979), 320–331.
• [2] P.C. Kainen, Complexity of products of even cycles, Bull. Inst. Combin. Appl. 62 (2011), 95–102.
• [3] S. Overbay, Generalized Book Embeddings, Fort Collins: Colorado State University Ph.D Thesis, 1998.
• [4] B. Zhao, Y Tian, and J Meng, Embedding semistrong product of paths and cycles in books, J. Nat. Sci. Hunan Norm. University 38(6) (2015), 73–77.
• [5] Z.L. Shao, X.L. Hao, and Z.G. Li, The book embedding of Schrijver graph, Utilitas Mathematica 107 (2018), 157–165.
• [6] X.L. Li, Book Embedding of Graphs, ZhengZhou: ZhengZhou University, 2002.
• [7] 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.

• [8] H. Enomoto, T. Nakamigawa T, and K. Ota, On the pagenumber of complete bipartite graphs, J. Combin. Theory Ser. B 71 (1997), 111–120.
• [9] P.C. Kainen, S Joslin, and S. Overbay, On dispersability of some circulant graphs, arXiv preprint arXiv:2109.10163.
• [10] P.C. Kainen and S. Overbay, Cubic planar bipartite graphs are dispersable, arXiv preprint arXiv:2107.04728.
• [11] S.S. Joslin, P.C. Kainen, and S. Overbay, On dispersability of some products of cycles, Missouri Journal of Mathematical Sciences 33(2) (2021): 206–213.
• [12] Z.L. Shao, H.R. Geng, and Z.G. Li, Matching book thickness of generalized Petersen graphs, Electron. J. Graph Theory Appl. 10(1) (2022), 173–180.
• [13] Z.L. Shao, Y.Q. Liu, and Z.G. Li, Bipartite cubic planar graphs are dispersable, arXiv preprint arXiv:2107.00907.
• [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] L.Z. Liu and Z.F. Zhang, On the structure properties and chromatics of pseudo Halin graphs, J. Lanzhou Railway University, 20(04) (2001), 105–107.
• [16] 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.