olivier@ut-emx.uucp (Olivier Goldschmidt) (05/02/91)
I'd like to know if you have some information on the following problem. Let me first define a probability space for directed random graphs. A graph drawn from the probability space G(k-in,k-out) is a labelled directed graph on n vertices. For every vertex i, we direct an arc from i to k vertices selected at random among the (n-1) other vertices and direct an arc from k vertices selected at random to i. Note that an arc (i,j) can be selected twice, once as an out-arc of i and once as an in-arc of j. The in-degree as well as the out-degree of a vertex is at least k, and the graph contains at most 2kn arcs. I am interested in a lower bound on k, say b(n), such that if k>=b(n), then a graph drawn from G(k-in,k-out) posesses a Hamiltonian cycle with high probability. Do you know of any such result? Thanks for your help. Olivier.