0
$\begingroup$

In the book embedding of a graph $G$ , each vertex of $G$ is placed on the spine and each edge is placed in the pages without crossing each other edge. If vertices have degree at most one in each page, the book embedding is matching . The minimum number of pages in which a graph can be matching book embedded is called matching book thickness. For Convenience, we denote the matching book thickness of a graph $G$ by $\mathrm{mbt}(G)$.

For the Cartesian product of a complete graph $K_n$ and a path $P_m$, I want to know $\mathrm{mbt}(K_n\Box P_m)$. Since $\mathrm{mbt}(K_n)=n$, it is not hard to see that $\mathrm{mbt}(K_n\Box P_2)=n+1,$ where $P_2=K_2$. For the case $ K_n\Box P_3$, I guess $\mathrm{mbt}(K_n\Box P_3)=n+2$. But I have no idea about the proof.

I will appreciate it if someone could give any suggestions.

$\endgroup$

1 Answer 1

1
$\begingroup$

The general problem of matching book thickness for the Cartesian product of a cycle and a complete graph is addressed in a preprint which just popped up on RGate from Feb 2, 2020 by Z. Shao, Y. Liu and Z. Li [1] (arXiv link)

It appears that they've answered your question. In fact, however, there is some additional information which I can provide.

[1] uses the theorem of Shannon Overbay, that dispersibility implies bipartiteness for a regular graph to obtain the lower bound which is then achieved by construction. The statements in the argument suggest that generalizations should be possible.

For Overbay's Theorem, see her thesis [2] at this link

The matching book thickness terminology is used in these slides "circLayouts.pdf" [3] of mine, where 'mbt' is determined for a class of circulant graphs.

The reference to "On book embeddings with degree-1 pages" in the arXiv paper should be replaced by "circLayouts.pdf". Ref.[3] was done using an older version of Mathematica by Wolfram Research, Inc. Unfortunately, the code is not currently functional and so the paper is "legacy" and has some key misprints: "Regular" was omitted from the conjecture on p. 5. A follow-up conjecture on p. 9 omitted "Bipartite." Finally, the figure is for n = 7, not n = 10.

$\endgroup$
1
  • $\begingroup$ @Kainen Thank you for the answer. I know the theorem of Shannon Overbay, that a regular and dispersalbe graph is bipartitite. It is valid for $K_n\Box C_m$ to obtain the lower bound $\Delta +1$ because their regularity and non-bipartiteness. It is easy to get $mbt(K_n\Box P_3)\leq n+2.$ But for the lower bound, i have no idea how to use Shannon's Theorem here for $K_n\Box P_3$ is not regular. Could you please explain it to me in detail? $\endgroup$ Feb 7, 2020 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.