Asymptotic enumeration of strongly connected digraphs by vertices and edges1. Issue 1 (26th April 2012)

• Record Type: Journal Article
• Authors: Pérez‐Giménez, Xavier; Wormald, Nicholas
• Is Part Of: Random structures & algorithms. Volume 43:Issue 1(2013)
• Page Start: 80
• Page End: 114
• Publication Date: 2012-04-26
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20416
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>We derive an asymptotic formula for the number of strongly connected digraphs with <italic>n</italic> vertices and <italic>m</italic> arcs (directed edges), valid for <italic>m</italic> ‐ <italic>n</italic> →<italic>∞</italic> as <italic>n</italic> →<italic>∞</italic> provided <italic>m</italic> = <italic>O</italic>(<italic>n</italic>log <italic>n</italic>). This fills the gap between Wright's results which apply to <italic>m</italic> = <italic>n</italic> + <italic>O</italic><xref ref-type="link" rid="eqn1">(1)</xref>, and the long‐known threshold for <italic>m</italic>, above which a random digraph with <italic>n</italic> vertices and <italic>m</italic> arcs is likely to be strongly connected. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013</p> </abstract>