3
$\begingroup$

Bondy-Chvátal theorem cannot be applied for directed graphs, is there any equivalent theorem that can be applied for them?

$\endgroup$
5
  • $\begingroup$ Bondy-Chvatal theorem is for undirected graphs. What do you mean by it cannot be applied for them? $\endgroup$
    – Saeed
    Apr 30, 2014 at 13:50
  • $\begingroup$ 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. $\endgroup$ Apr 30, 2014 at 14:59
  • $\begingroup$ 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 $\endgroup$ Apr 30, 2014 at 15:33
  • $\begingroup$ Now I see you talking about digraphs, in that case I really recommend you to read chapter 6 of this 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). $\endgroup$
    – Saeed
    Apr 30, 2014 at 17:51
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Apr 30, 2014 at 19:04

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.