Back to Search
Start Over
Counting Hamilton cycles in sparse random directed graphs
- Source :
- Random Structures & Algorithms, 53 (4), Proceedings of the Eighteenth International Conference “Random Structures and Algorithms”
- Publication Year :
- 2018
- Publisher :
- Wiley, 2018.
-
Abstract
- Let D(n,p) be the random directed graph on n vertices where each of the n(n-1) possible arcs is present independently with probability p. A celebrated result of Frieze shows that if $p\ge(\log n+\omega(1))/n$ then D(n,p) typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in D(n,p) is typically $n!(p(1+o(1)))^{n}$. We also prove a hitting-time version of this statement, showing that in the random directed graph process, as soon as every vertex has in-/out-degrees at least 1, there are typically $n!(\log n/n(1+o(1)))^{n}$ directed Hamilton cycles.
- Subjects :
- Random graph
Applied Mathematics
General Mathematics
010102 general mathematics
0102 computer and information sciences
Directed graph
Binary logarithm
01 natural sciences
Computer Graphics and Computer-Aided Design
Omega
Hamiltonian path
Vertex (geometry)
Combinatorics
symbols.namesake
010201 computation theory & mathematics
symbols
FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
Directed Graph
Hamilton cycle
0101 mathematics
Software
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms, 53 (4), Proceedings of the Eighteenth International Conference “Random Structures and Algorithms”
- Accession number :
- edsair.doi.dedup.....93afa92f1bf595a0dd1d7265a7b5fc4e