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.



Matching book embedding of Cartesian products of graphs
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](https://arxiv.org/abs/2002.00309))


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](https://connect.gonzaga.edu/asset/file/540/Thesis-GeneralizedBookEmbeddings-Overbay.pdf)


The matching book thickness terminology is used in [these slides "circLayouts.pdf"](http://faculty.georgetown.edu/kainen/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. 


