2
$\begingroup$

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$ with a set of chords $D$. Is it always possible to add a chord $f$ of $C$ in $G$ so that the resulting graph has a Hamiltonian circuit containing all the chords (including the new chord $f$)? Or equivalently, is there a Hamiltonian path containing all the chords in D? 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 chords in the original set? Or equivalently, let $G$ be a 4-regular Hamiltonian graph $G$ with a Hamiltonian circuit $C$, and such that the chords of $C$ can be partitioned into two perfect matchings $P$, $Q$. Is there a Hamiltonian circuit of $G$ which contains all the edges in $P$ ($Q$). If not, under what conditions is this true?

Computer experiments seem to suggest this might be the case.

$\endgroup$
1
$\begingroup$

The answer to question 1 is no. Here are examples of hamiltonian cubic graphs without a hamilton path that contains all the chords of a hamiltonian circuit. They are smallest possible (there are no examples of graphs with fewer vertices for which the answer to the question is no ... this was exhaustively checked).

examples

Question 2 remains open.

| cite | improve this answer | |
$\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.