Asymptotic enumeration of strongly connected digraphs by vertices and edges

2010/05/07 by Xavier Perez-Gimenez, Perez-Gimenez, Xavier, Nicholas Wormald +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1005.1285

35 pages

arxiv created 2011/05/17 · arxiv updated 2011/05/18

Abstract

We derive an asymptotic formula for the number of strongly connected digraphs with n vertices and m arcs (directed edges), valid for m-n→∞ as n→ ∞ provided m=O(nlog n). This fills the gap between Wright's results which apply to m=n+O(1), and the long-known threshold for m, above which a random digraph with n vertices and m arcs is likely to be strongly connected.

Related

• Counting strongly-connected, sparsely edged directed graphs
• The number of edges in critical strongly connected graphs
• Counting directed acyclic and elementary digraphs
• Counting strongly connected (k₁,k₂)-directed cores
• Counting Connected Graphs Asymptotically