0
$\begingroup$

I'm currently confused whether a graph should contain strictly one distinct Hamiltonian Cycle. (given that [1,2,3,4,1] and [2,3,4,1,2] are the same).

I was wondering if, by definition, there can be multiple distinct Hamiltonian Cycles in a graph? something like H1 = [1,2,3,1] and H2 = [6,7,8,6]

can someone kindly confirm?

(addt'l sources and references would really be great so I can dive in deeper)

Cheers!

$\endgroup$
  • $\begingroup$ In your second example, H1 and H2 can't be Hamiltonian cycles in the same graph since a Hamiltonian cycle includes every vertex exactly once. In your first example, the two cycles could be distinct Hamiltonian cycles in a complete graph on 4 vertices. $\endgroup$ – Juho May 19 '15 at 15:54
  • $\begingroup$ I see.. so for the second example, H1 and H2 would simply be called cycles right? is there a distinct name for cycles that doesn't contain same vertices? $\endgroup$ – Kevin Lloyd Bernal May 19 '15 at 16:00
  • $\begingroup$ If you want to, you can call them vertex-disjoint cycles (i.e. they don't share any vertices). $\endgroup$ – Juho May 19 '15 at 16:17
2
$\begingroup$

Recall a Hamiltonian cycle visits each vertex of a graph exactly once. Thus, the cycles H1 and H2 in your second example can't be Hamiltonian cycles in the same graph.

In your first example, the two cycles could be distinct Hamiltonian cycles in e.g. the complete graph on 4 vertices. That is to say, there can definitely be multiple Hamiltonian cycles in a graph.

If you care about naming conventions, you can call two cycles that don't share any vertices vertex-disjoint cycles. Similarly, two cycles can be edge-disjoint if they don't share edges.

$\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.