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 Wheel graph $W_n$ with $n$ vertices $O,1,2,3,...,n-1$, I want to know $\mathrm{mbt}(W_n)$. For the case $n$ is odd, it is not hard to know that $\mathrm{mbt}(W_n)=\Delta(W_n)=n-1.$ For the case $n$ is even, I guess $\mathrm{mbt}(W_n)=n$. For example, when $n=6$, I have tried some matching book embeddings of $W_6$ with different orderings $\omega$ of the vertices on the spine. And I always get a matching book embedding on 6-page. For $W_4=K_4$, $mbt(W_4)=4.$ But I was wondering whether the equality holds for any even $n$,i.e.$\mathrm{mbt}(W_n)=n$ .

I will appreciate it if someone could give any suggestions.

enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$

I believe this is a counterexample:

Let the vertices be ordered 1, 2, 3, 4, 5, 6 on the spine.

Page 1: 4-6, 2-1

Page 2: 6-1, 2-4

Page 3: 1-5, 2-3

Page 4: 5-3, 2-6

Page 5: 3-4, 2-5

$\endgroup$
2
  • $\begingroup$ Good job. Thanks a lot. $\endgroup$ Commented Jun 17, 2020 at 0:36
  • $\begingroup$ How do you think about this problem? $\endgroup$ Commented Jun 17, 2020 at 11:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .