14
$\begingroup$

Call a graph $G$ $n$-almost-Hamiltonian if there is a closed walk in $G$ that visits every vertex of $G$ exactly $n$-times. So a Hamiltonian graph is $n$-almost-Hamiltonian for all $n$. Are all cubic graphs $n$-almost-Hamiltonian for some sufficiently large $n$?

$\endgroup$
15
$\begingroup$

Yes, every connected cubic graph is 3-almost-Hamiltonian. Replace each edge by two parallel edges then follow an Eulerian circuit.

In the case of a bridgeless cubic graph, you can add a perfect matching instead of doubling each edge, which shows they are 2-almost-Hamiltonian.

$\endgroup$
  • $\begingroup$ Your answer makes clear that every connected graph is $n$-almost Hamiltonian for all even $n$. Is there a chance that some graphs, such as all cubic graphs, are $n$-almost Hamiltonian for some odd $n$? $\endgroup$ – Menachem Feb 4 '19 at 8:02
  • 5
    $\begingroup$ @Menachem I gave the example $n=3$. Also note that my proof only works easily for regular graphs. Many graphs, for example an unbalanced bipartite graph, are not $n$-almost Hamiltonian for any $n$. $\endgroup$ – Brendan McKay Feb 4 '19 at 9:15

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.