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

You must log in to answer this question.

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