The matching book embedding under some graph operations

Zeling Shao, Min Yao, Zhiguo Li

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

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.13

References

F. Bernhart and P. C. Kainen, "The Book Thickness of a Graph," Journal of Combinatorial Theory, Series B, vol. 27, pp. 320–331, 1979.

F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg, "Embedding graphs in books: a layout problem with applications to VLSI design," SIAM Journal on Algebraic Discrete Methods, vol. 8, no. 1, pp. 33–58, 1987.

N. Khan, V. S. Rao, and S. Lim, "Development of 3-D silicon module with TSV for system in packaging," IEEE Transactions on Components and Packaging Technologies, vol. 33, no. 1, pp. 3–9, 2020.

B. Zhao, W. Chen, J. Meng, and F. Liu, "Book embedding of complex network with community structure," Applied Mathematics and Computation, vol. 361, pp. 747–751, 2019.

W. Liang, "Human Genome Book: Words, Sentences and Paragraphs," arXiv preprint arXiv:2501.16982.

X. Guan, C. Wu, W. Yang, and J. Meng, "A survey on book-embedding of planar graphs," Frontiers of Mathematics in China, vol. 17, no. 2, pp. 255–273, 2022.

S. B. Overbay, "Generalized Book Embeddings," Colorado State University, 1998.

C. McLeman and E. McNicholas, "Spectra of coronae," Linear Algebra and its Applications, vol. 435, no. 5, pp. 998–1007, 2011.

J. A. Bondy and U. S. R. Murty, Graph Theory, Springer Publishing Company, Incorporated, 2008.

S. Nada, A. Elrokh, E. A. Elsakhawi, and D. E. Sabra, "The corona between cycles and paths," Journal of the Egyptian Mathematical Society, vol. 25, no. 2, pp. 111–118, 2017.

S. W. Saputro, N. Mardiana, and I. A. Purwasih, "The metric dimension of comb product graphs," Matematicki Vesnik, vol. 69, no. 4, pp. 248–258, 2017.

S. Pupyrev, "Book embeddings of graph products," arXiv preprint arXiv:2007.15102.

P. C. Kainen, "Complexity of products of even cycles," Bulletin of the Institute of Combinatorics and its Applications, vol. 62, pp. 95–102, 2011.

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, vol. 153, pp. 89–97, 2020.

S. S. Joslin, P. C. Kainen, and S. Overbay, "On dispersability of some products of cycles," Missouri Journal of Mathematical Sciences, vol. 33, no. 2, pp. 206–213, 2021.

Z. L. Shao, X. X. Yu, and Z. G. Li, "On the dispersability of odd toroidal grids," Applied Mathematics and Computation, vol. 453, 128087, 2023.

Z. L. Shao, H. R. Geng, and Z. G. Li, "Matching book thickness of generalized Petersen graphs," Electronic Journal of Graph Theory and Applications, vol. 10, no. 1, pp. 173–180, 2022.

Z. L. Shao, H. R. Geng, and Z. G. Li, "The matching book embeddings of pseudo-Halin graphs," Electronic Journal of Graph Theory and Applications, vol. 11, no. 1, pp. 317–327, 2023.

X. X. Yu, Z. L. Shao, and Z. G. Li, "On the classification and dispersability of circulant graphs with two jump lengths," Discrete Applied Mathematics, vol. 355, pp. 268–286, 2024.

Z. L. Shao, Y. Q. Cui, and Z. G. Li, "The dispersability of the Kronecker cover of the product of complete graphs and cycles," Electronic Journal of Graph Theory and Applications, vol. 12, no. 1, pp. 117–123, 2024.

Y. Yuan, X. Geng, W. Yang, and X. Guan, "A Note on Matching Book Embedding of the Cartesian Product of a Uni-chord Cycle and a Cycle," Journal of Interconnection Networks, 2550011, 2025.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats