Bondy-Chvátal theorem cannot be applied for directed graphs, is there any equivalent theorem that can be applied for them?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Bondy-Chvatal theorem is for undirected graphs. What do you mean by it cannot be applied for them? $\endgroup$– SaeedApr 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$– Paweł KaftanApr 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$– Marzio De BiasiApr 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$– SaeedApr 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$– SaeedApr 30, 2014 at 19:04
Add a comment
|