Counting strongly‐connected, moderately sparse directed graphs. Issue 1 (6th June 2012)

• Record Type: Journal Article
• Authors: Pittel, Boris
• Is Part Of: Random structures & algorithms. Volume 43:Issue 1(2013)
• Page Start: 49
• Page End: 79
• Publication Date: 2012-06-06
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20433
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>A sharp asymptotic formula for the number of strongly connected digraphs on <italic>n</italic> labelled vertices with <italic>m</italic> arcs, under the condition <italic>m</italic> ‐ <italic>n</italic> ≫ <italic>n</italic>^2/3, <italic>m</italic> = <italic>O</italic>(<italic>n</italic>), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on <italic>n</italic> vertices with <italic>m</italic> 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 by counting first 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 <italic>m</italic> and <italic>n</italic> among all such digraphs with positive in/out‐degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013</p> </abstract>