<p><a href="http://en.wikipedia.org/wiki/Hamiltonian_path#Bondy.E2.80.93Chv.C3.A1tal_theorem" rel="nofollow" >Bondy-Chvátal theorem</a> cannot be applied for directed graphs, is there any equivalent theorem that can be applied for them?</p>

CC BY-SA 3.0
2014-04-30T13:50:54.067Z
Bondy-Chvatal theorem is for undirected graphs. What do you mean by it cannot be applied for them?
Saeed
CC BY-SA 3.0
2014-04-30T14:59:32.010Z
I'm sorry. I confused names. I deleted an incorrect comment. I meant "directed" instead of "undirected". So this directed graph represented by adjacency list doesn't contain Hamiltonian cycle: 0: 2; 1: 0 2; 2: 0; Closure contains Hamiltonian cycle: 0: 1 2; 1: 0 2; 2: 0 1 so I assume Bondy-Chvátal theorem cannot be applied for directed graphs.
Paweł Kaftan
CC BY-SA 3.0
2014-04-30T15:33:48.163Z
You can find some related recent results/unsolved conjectures in the second chapter of the recent (2010) survey: [Daniela Kühn and Deryk Osthus, A survey on Hamilton cycles in directed graphs](http://arxiv.org/abs/1006.0590)
Marzio De Biasi
CC BY-SA 3.0
2014-04-30T17:51:01.760Z
Now I see you talking about digraphs, in that case I really recommend you to read chapter 6 of [this](http://www.cs.rhul.ac.uk/books/dbook/main.pdf) book, but latest version (second edition which is for 2009). Unfortunately it's not available online. But if you look at Marzio's reference, Conjecture 5 is almost what you need. Means that at least upto that time no one proved this. (definition of closure in digraph depends to personal tast, and I think that conjecture is almost close to what you looking for).
Saeed
CC BY-SA 3.0
2014-04-30T19:04:56.780Z
P.S: I gave a little thought about the problem, I find that it is not easy to generalize it to digraphs, both finding a good definition and claims and also proving them is not easy extension of undirected cases, interesting problem.
Saeed
<graph-theory>
Is there any equivalent for Bondy-Chvátal theorem for directed graphs?
Paweł Kaftan
# Is there any equivalent for Bondy-Chvátal theorem for directed graphs?

(Asked by: username_0 on 2014-04-30)

[Bondy-Chvátal theorem](http://en.wikipedia.org/wiki/Hamiltonian_path#Bondy.E2.80.93Chv.C3.A1tal_theorem) cannot be applied for directed graphs, is there any equivalent theorem that can be applied for them?

**Tags:** graph-theory
> **Comments:**
> **username_1**: Bondy-Chvatal theorem is for undirected graphs. What do you mean by it cannot be applied for them?  
> **username_0**: I'm sorry. I confused names. I deleted an incorrect comment. I meant "directed" instead of "undirected". So this directed graph represented by adjacency list doesn't contain Hamiltonian cycle: 0: 2; 1: 0 2; 2: 0; Closure contains Hamiltonian cycle: 0: 1 2; 1: 0 2; 2: 0 1 so I assume Bondy-Chvátal theorem cannot be applied for directed graphs.  
> **username_2**: You can find some related recent results/unsolved conjectures in the second chapter of the recent (2010) survey: [Daniela Kühn and Deryk Osthus, A survey on Hamilton cycles in directed graphs](http://arxiv.org/abs/1006.0590)  
> **username_1**: Now I see you talking about digraphs, in that case I really recommend you to read chapter 6 of [this](http://www.cs.rhul.ac.uk/books/dbook/main.pdf) book, but latest version (second edition which is for 2009). Unfortunately it's not available online. But if you look at Marzio's reference, Conjecture 5 is almost what you need. Means that at least upto that time no one proved this. (definition of closure in digraph depends to personal tast, and I think that conjecture is almost close to what you looking for).  
> **username_1**: P.S: I gave a little thought about the problem, I find that it is not easy to generalize it to digraphs, both finding a good definition and claims and also proving them is not easy extension of undirected cases, interesting problem.  

---

## 0 answers

