A cycle plus triangles graph is a 4-regular graph $G$ with a Hamiltonian circuit $C$ and such that the chords of $C$ induce a set of disjoint triangles (3-circuits). A 4-regular graph $G$ has a Hamilton decomposition if its set of edges can be partitioned into two sets that induce Hamiltonian circuits in $G$. A cycle plus triangles graph is edge 3-connected if it doesn’t have any edge 2-cuts (sets of two edges which when removed disconnect the graph).

Our question is the following

Question Let $G$ be a cycle plus triangles graph which is edge 3-connected. Is it true then that $G$ has a Hamiltonian decomposition, or is there a counterexample that might be known?

  • 1
    $\begingroup$ As a minor comment, a 4-regular graph which is 3-edge-connected is automatically 4-edge-connected: by counting odd-degree vertices, there cannot be a partition $V(G) = S \cup T$ with exactly 3 (or any other odd number) of edges between $S$ and $T$. $\endgroup$ – Misha Lavrov Nov 24 '19 at 17:10
  • $\begingroup$ @MishaLavrov Thank you! $\endgroup$ – EGME Nov 24 '19 at 17:33
  • $\begingroup$ @MishaLavrov I couldn’t find cases of even order which are class 2 yet. $\endgroup$ – EGME Nov 27 '19 at 5:28
  • $\begingroup$ @MishaLavrov I now checked the example in the answer $\endgroup$ – EGME Nov 27 '19 at 7:33

All edge 3-connected cycle plus triangles graph with 18 or fewer vertices have Hamiltonian decompositions. However, the graph in the picture below with 21 vertices is edge 3-connected and does not have a hamiltonian decomposition. It got derived from a counterexample to another hamiltonicity conjecture made some years ago about a class of cubic graphs (MO-graphs, cubic graphs with a chordless dominating circuit); the example was found by Brendan McKay - the derivation entails replacing dominated vertices by triangles. From 21 vertices onwards there seem to be counterexamples of every possible order. There would seem to be a relation between hamiltonian MO-graphs and cycle plus triangles which have a hamiltonian decomposition, but we are unable to establish it at present or be more specific about it.


| cite | improve this answer | |

Your Answer

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

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