A scaling limit for the length of the longest cycle in a sparse random digraph

DOI10.1002/rsa.21030zbMath1522.05076arXiv2001.06481OpenAlexW3171281872MaRDI QIDQ6074672

Michael Anastos, Alan M. Frieze

Publication date: 12 October 2023

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

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

zbMATH Keywords

scaling limitlongest cyclerandom digraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Combinatorial probability (60C05) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Density (toughness, etc.) (05C42)

Related Items

Depth first exploration of a configuration model, A note on long cycles in sparse random graphs, Cycle lengths in sparse random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On large matchings and cycles in sparse random graphs
• Probabilistic methods for algorithmic discrete mathematics
• Hamilton cycles in a class of random directed graphs
• A scaling limit for the length of the longest cycle in a sparse random graph
• Longest cycles in sparse random digraphs
• The transitive closure of a random digraph
• Almost all graphs with 1.44n edges are 3-colorable
• Clutter percolation and random graphs
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence