Counting Hamilton cycles in sparse random directed graphs

DOI10.1002/RSA.20815MaRDI QIDQ4625019zbMATH OpenOpenAlexWikidataFDO

Authors Asaf Ferber, Matthew Kwan, Benny Sudakov

Publication date 20 February 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

directed graphHamilton cyclerandom graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42) Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

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 $pge(logn+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!(logn/n(1+o(1)){)}^n$ directed Hamilton cycles.

Recommendations

• Packing, counting and covering Hamilton cycles in random directed graphs
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Hamilton cycles in a class of random directed graphs

Cited in

(10)

• Getting a directed Hamilton cycle two times faster
• scientific article; zbMATH DE number 1496581 (Why is no real title available?)
• Packing arborescences in random digraphs
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Spanning cycles in random directed graphs
• Number of subgraphs and their converses in tournaments and new digraph polynomials
• First cycles in random directed graph processes

This page was built for publication: Counting Hamilton cycles in sparse random directed graphs

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