Asymptotic enumeration of strongly connected digraphs by vertices and edges1. Issue 1 (26th April 2012) - Pérez‐Giménez, Xavier; Wormald, Nicholas
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. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013