0
$\begingroup$

I'm trying to prove that one concrete directed graph has no Hamiltonian cycle, but didn't seem to find any relevant theorems

Improve this question
$\endgroup$
2
  • $\begingroup$ A weak necessary condition is having no directed cuts. This is a set of vertices X such that all arcs with one end in X either all leave X or all enter X. $\endgroup$
    – Tony Huynh
    Commented Jun 8, 2021 at 0:21
  • $\begingroup$ It's got to be connected... But the main relevant theorem is that testing for the existence of a Hamiltonian cycle is, in general, NP-complete; so unless P=NP it doesn't scale well. $\endgroup$
    – Peter Taylor
    Commented Jun 8, 2021 at 7:15

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .