2010/05/03 by Boris Pittel, Pittel, Boris
Mathematics · #05C80 #60K35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C80 #msc:60K35
paper · pdf · doi:10.48550/arxiv.1005.0327
32 pages
arxiv created 2010/05/05 · arxiv updated 2010/05/07
A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under a condition m-n→∞, m=O(n), is obtained; this solves a problem posed by Wright back in 1977. Our formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula via counting two-connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly-connected digraphs with parameters m and n among all such digraphs with positive in/out-degrees.