Crossing number of 3-regular graphs

61 Views Asked by At

What's the largest possible crossing number for a $3$-regular graph? And what about the largest crossing number for a $3$-regular Hamiltonian graph?

1

There are 1 best solutions below

0
On

This is what you can extract from here for cubic graphs of small orders: $$ \begin{array}{c|ccc} {\rm Number\ of\ vertices} & {\rm Largest\ crossing\ number} \\ \hline 2,4 & 0 \\ 6,8 & 1 \\ 10,12 & 2 \\ 14 & 3\\ 16 & 4\\ 18 & 5\\ 20 & 6\\ 22 & 7\\ 24 & 8\\ 26 & [8,10]\\ 28 & [11,13]\\ 30 & \geq 13 \end{array} $$ Some other inequalities on the number of crossings of a graph are known, which allow you to estimate your number as well. You can find a lot of literature on a topic close to you at these links.

I think your second question could be answered in about the same way. You just need to look carefully at the minimal examples - they all seem to be Hamiltonian.

I hope this answer helped you a little, though of course it looks more like a long comment.