Matching book thickness of generalized Petersen graphs
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
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2022.10.1.11
References
Bernhart F, Kainen P C. The book thickness of a graph[J]. Journal of Combinatorial Theory, Series B, 1979, 27: 320-331.
Chung F R K, Leighton F T, Rosenberg A L. Embedding graphs in books: a layout problem with applications to VLSI design[J]. Society for Industrial and Applied Mathematics, 1987, 8(1): 33-58.
Akitaya H A, Demaine E D, Hesterberg A. Upward partitioned book embbeddings[J]. Lecture Notes in Computer Science, 2017, 10692: 210-223.
Zhao B, Xiong W, Tian Y Z. Embedding generalized Petersen graph in books[J]. Chinese Annals of Mathematics, Series B, 2016, 37(3): 385-394.
Shao Z L, Qi C Y, Li Z G. Book embedding of graph bundles over a cycle with claw as a fibre[J]. Utilitas Mathematica, 2020,116:33-44.
Yang J, Shao Z L, Li Z G. Embedding cartesian product of some graphs in books[J]. Communications in Mathematical Research, 2018, 34(03): 253-260.
Yannakakis M. Planar graphs that need four pages[J]. Journal of Combinatorial Theory, Series B, 2020, 145: 241-263.
Overbay S. Generalized book embeddings[D]. Fort Collins: Colorado State University, 1998.
Kainen P C. Complexity of products of even cycles[J]. Bulletin of the Institute of Combinatorics and Its Applications, 2011, 62: 95-102.
Shao Z L, Liu Y Q, Li Z G. Matching book embedding of the cartesian product of a complete graph and a cycle[J]. Ars Combinatoria, 2020, 153: 89-97.
Kainen P C, Overbay S. Cubic planar bipartite graphs are dispersable[J]. arXiv preprint arXiv:2107.04728, 2021.
Shao Z L, Geng H R, Li Z G. Matching book thickness of Halin graphs[J]. arXiv preprint arXiv:2008.13331, 2020.
Watkins M E, A theorem on tait colorings with an application to the generalized Petersen graphs[J]. Combinatorial Theory, 1969, 6: 152-164.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.