Packing, Counting and Covering Hamilton cycles in random directed graphs
Preprint
Abstract
A Hamilton cycle in a digraph is a cycle that passes through all the vertices, where all the arcs are oriented in the same direction. The problem of finding Hamilton cycles in directed graphs is well studied and is known to be hard. One of the main reasons for this, is that there is no general tool for finding Hamilton cycles in directed graphs comparable to the so called Pos?a `rotation-extension' technique for the undirected analogue. Let ${\mathcal D}(n,p)$ denote the random digraph on vertex set $[n]$, obtained by adding each directed edge independently with probability $p$. Here, we present a general and a very simple method, using known results, to attack problems of packing and counting Hamilton cycles in random directed graphs, for every edge-probability $p>\log^C(n)/n$. Our results are asymptotically optimal with respect to all parameters and apply equally well to the undirected case.
Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Random directed graphs are robustly HamiltonianRandom Structures & Algorithms, 2015
- Optimal covers with Hamilton cycles in random graphsCombinatorica, 2014
- Edge-disjoint Hamilton cycles in random graphsRandom Structures & Algorithms, 2013
- On covering expander graphs by hamilton cyclesRandom Structures & Algorithms, 2012
- Hamiltonian cycles in Dirac graphsCombinatorica, 2009
- On two Hamilton cycle problems in random graphsIsrael Journal of Mathematics, 2008
- The solution of van der Waerden's problem for permanentsAdvances in Mathematics, 1981
- Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrixMathematical Notes, 1981
- A Hamiltonian decomposition of K2m∗, 2m ≥ 8Journal of Combinatorial Theory, Series B, 1980
- Hamiltonian circuits in random graphsDiscrete Mathematics, 1976