0
$\begingroup$

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?

$\endgroup$
4
  • 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$ Nov 24, 2019 at 17:10
  • $\begingroup$ @MishaLavrov Thank you! $\endgroup$
    – EGME
    Nov 24, 2019 at 17:33
  • $\begingroup$ @MishaLavrov I couldn’t find cases of even order which are class 2 yet. $\endgroup$
    – EGME
    Nov 27, 2019 at 5:28
  • $\begingroup$ @MishaLavrov I now checked the example in the answer $\endgroup$
    – EGME
    Nov 27, 2019 at 7:33

1 Answer 1

0
$\begingroup$

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.

example

$\endgroup$

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.