Examples of non-hamiltonian decomposable graphs

Question

Good Afternoon!

I read that Line graph of the Petersen graph is 4-regular 4-edge-connected and non-hamiltonian decomposable. Does someone knows examples (or references) of non-hamiltonian decomposable graphs?

Thanks

Answer 1

Two obvious necessary conditions for a graph to be Hamilton decomposable are:

• it is Hamiltonian (which implies it is connected), and
• it is regular with even vertex degrees (since Hamilton cycles are $2$-regular).

Any graph that does not satisfy all three of these conditions will not be Hamilton decomposable.

---

In response to the comment: $C_2 \times C_3$ (where $\times$ is the Cartesian product) has $$|V(C_3)| \times |E(C_2)|+|V(C_2)| \times |E(C_3)|=9$$ edges. It can't be Hamilton decomposable since the number of edges is not divisible by $|V(C_2 \times C_3)|=6$.

Answer 2

I had written code to find Hamiltonian decompositions (HD) and thought that, with only small counterexamples, all vertex transitive (VT) graphs would be HD. Not so, as was recently proved. It is well known that there are five (connected) VT graphs that are not Hamiltonian. I had conjectured that every Hamiltonian VT graph is HD except the line graph of the Petersen graph. I checked that the conjecture is true for all VT graphs with vertex count up to 30. Seemed like good evidence. Nope. The conjecture is false. Bryant and Dean recently showed how to construct counterexamples. See: http://arxiv.org/abs/1408.5211