Getting directed Hamilton cycle twice faster

Details Getting directed Hamilton cycle twice faster Getting directed Hamilton cycle twice faster

2011-03-29

arxiv.org/abs/1103.5522v3

Mathematics

Combinatorics

Scientific paper

Consider the random graph process where we start with an empty graph on n vertices, and at time t, are given an edge e_t chosen uniformly at random among the edges which have not appeared so far. A classical result in random graph theory asserts that w.h.p. the graph becomes Hamiltonian at time (1/2+o(1))n log n. On the contrary, if all the edges were directed randomly, then the graph has a directed Hamilton cycle w.h.p. only at time (1+o(1))n log n. In this paper we further study the directed case, and ask whether it is essential to have twice as many edges compared to the undirected case. More precisely, we ask if at time t, instead of a random direction one is allowed to choose the orientation of e_t, then whether it is possible or not to make the resulting directed graph Hamiltonian at time earlier than n log n. The main result of our paper answers this question in the strongest possible way, by asserting that one can orient the edges on-line so that w.h.p., the resulting graph has a directed Hamilton cycle exactly at the time at which the underlying graph is Hamiltonian.

Affiliated with

Also associated with

No associations

Rating

Getting directed Hamilton cycle twice faster does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Getting directed Hamilton cycle twice faster, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Getting directed Hamilton cycle twice faster will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-162529