Skip to main content
2 of 5
added 294 characters in body
EGME
  • 1k
  • 8
  • 14

Hamiltonian cycles containing all chords of a given Hamiltonian cycle in almost cubic Hamiltonian graphs

Let $G$ be a simple cubic graph which has a Hamiltonian circuit $C$. In general, it is not possible to find a second Hamiltonian circuit which contains all the chords of $C$. For example, the Wagner graph with $C$ being the outer circuit in the picture contains no such second Hamiltonian circuit.

Wagner graph

But it is possible to add an additional chord so that the resulting graph contains a second Hamiltonian circuit including all chords, as in the second picture?

Wagner with chord

Our first question is:

Question 1 (EGME) Let $G$ be a cubic graph which has a Hamiltonian circuit $C$. Is it always possible to add a chord of $C$ in $G$ so that the resulting graph has a Hamiltonian circuit containing all the chords? Please provide proof or counterexample.

Our second question is

Question 2 (EGME) If we add ANY new set of chords of $C$ in $G$ (as in question 1) which are a perfect matching in the resulting graph (which should be simple), is there a second Hamiltonian circuit which contains all of the original set of chords?

Computer experiments seem to suggest this might be the case.

EGME
  • 1k
  • 8
  • 14