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$
3
  • $\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, 2015 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$ May 19, 2015 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, 2015 at 16:17

1 Answer 1

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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.