An MO graph is a simple cubic graph with a chordless dominating circuit (that is, a circuit which has no chords and which, if deleted, leaves behind a set of isolated vertices). In a previous post (Edge colorability and Hamiltonicity of certain classes of cubic graphs (MO graphs)) I asked if these graphs are Hamiltonian, and in his answer to the same post, Brendan McKay provided some examples showing that this is not the case. After looking at those counterexamples and other ones we have found none that are cyclically 4-connected. There is some explanation as to why MO graphs that are not cyclically 4-connected could fail to be hamiltonian, but we see no explanation for cyclically 4-connected ones failing to be Hamiltonian. Our question is:

Question Can someone supply an example of a cyclically 4-connected MO graph which is NOT Hamiltonian? Or could it be that all these graphs are Hamiltonian?

My guess is that these graphs are Hamiltonian, but I don’t have the tools to look for counterexamples. I know that a counterexample must have at least 28 vertices. I would love to be proved wrong!

This question is closely related to a couple of questions about cycles plus triangle graphs which I will post separately.

The graph below shows Brendan's first non-Hamiltonian example with an edge 3-cut highlighted in red:

Brendan's example


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.