The dispersability of the Kronecker cover of the product of complete graphs and cycles

Zeling Shao, Yaqin Cui, Zhiguo Li

Abstract


The Kronecker cover of a graph G is the Kronecker product of G and K2. The matching book embedding of a graph G is an embedding of G with the vertices on the spine, 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 embeddding of G and it denoted by mbt(G). A graph G is dispersable if mbt(G)=Δ(G), nearly dispersable if mbt(G)=Δ(G)+1. In this paper, the dispersability of the Kronecker cover of the Cartesian product of complete graphs Kp and cycles Cq is determined.


Keywords


matching book embedding, matching book thickness, Kronecker cover, complete graph, cycle

Full Text:

PDF

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

References

F. Bernhart and P.C. Kainen, The book thickness of a graph, Journal of Combinatorial Theory, Series B, 27 (1979), 320–331.

J.A.Bondy and U.S.R. Murty, Graph Theory, London: Springer, 2008.

W. Fulton, Covering spaces. In: Algebraic Topology. Graduate Texts in Mathematics, vol 153. Springer, New York, NY. 1995: 153–154.

P.C. Kainen, Complexity of products of even cycles, Bulletin of the Institute of Combinatorics and Its Applications 62 (2011), 95–102.

S. Overbay, Generalized Book Embeddings, Ph. D. thesis, Fort Collins: Colorado State University, 1998.

Z. Shao, H. Geng, and Z. Li, Matching book thickness of generalized Petersen graphs. Electronic Journal of Graph Theory and Applications 10 (1) (2022), 173–180.

Z. Shao, Y. Liu, and Z. Li, Matching book embedding of the cartesian product of a complete graph and a cycle, Ars Combinatoria, 153 (2020), 89–97.

Z. Shao, X. Yu, and Z. Li, On the dispersability of odd toroidal grids, Applied Mathematics and Computation, 453 (2023), 128087.

D. Waller, Double covers of graphs. Bulletin of the Australian Mathematical Society, 14 (2) (1976), 233–248.

J. Yang, Z. Shao, and Z. Li, Embedding cartesian product of some graphs in books, Communications in Mathematical Research 34(03) (2018), 253-260.


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