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$?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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.
answered Feb 4 '19 at 6:40
-
$\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
