Getting a directed Hamilton cycle two times faster

DOI10.1017/S096354831200020XMaRDI QIDQ2911073zbMATH OpenOpenAlexFDO

Authors Choongbum Lee, Dan Vilenchik, Benny Sudakov

Publication date 12 September 2012

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.5522

zbMATH Keywords

directed graphrandom graph processdirected Hamiltonian cycle

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Abstract: 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.

Recommendations

• Packing directed Hamilton cycles online
• Counting Hamilton cycles in sparse random directed graphs
• How many random edges make a dense graph hamiltonian?
• An algorithm for finding hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs

Cites work

• scientific article; zbMATH DE number 1496581 (Why is no real title available?)
• Almost all regular graphs are hamiltonian
• An algorithm for finding hamilton cycles in random directed graphs
• Avoiding a giant component
• Avoiding small subgraphs in Achlioptas processes
• Balanced Allocations
• Birth control for giants
• Creating a Giant Component
• Embracing the giant component
• Hamilton cycles in a class of random directed graphs
• Hamilton cycles in random geometric graphs
• Hamiltonian circuits in random graphs
• Hamiltonicity thresholds in Achlioptas processes
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• On some problems of a statistical group-theory. I

Cited in

(6)

• scientific article; zbMATH DE number 1563195 (Why is no real title available?)
• Hamiltonicity thresholds in Achlioptas processes
• Packing Hamilton cycles online
• Spanning cycles in random directed graphs
• Packing directed Hamilton cycles online
• First cycles in random directed graph processes

This page was built for publication: Getting a directed Hamilton cycle two times faster

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2911073)