Counting strongly-connected, moderately sparse directed graphs

DOI10.1002/RSA.20433MaRDI QIDQ2844082zbMATH OpenOpenAlexFDO

Authors Boris Pittel

Publication date 27 August 2013

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.0327

zbMATH Keywords

asymptoticsenumerationdirected graphsstrongly connected

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Connectivity (05C40)

Abstract: A sharp asymptotic formula for the number of strongly connected digraphs on $n$ labelled vertices with $m$ arcs, under a condition $m-noinfty$, $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.

Recommendations

• Asymptotic enumeration of strongly connected digraphs by vertices and edges
• Asymptotic enumeration of sparse 2-connected graphs
• The number of \(h\)-strongly connected digraphs with small diameter
• Connectivities of random circulant digraphs
• Counting directed acyclic and elementary digraphs

Cites work

• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 166082 (Why is no real title available?)
• scientific article; zbMATH DE number 1139976 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Airy phenomena and analytic combinatorics of connected graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Asymptotic enumeration of sparse graphs with a minimum degree constraint
• Component behavior near the critical point of the random graph process
• Corrigendum to ``Counting connected graphs inside-out [J. Comb. Theory, Ser. B 93, No. 2, 127--172 (2005; Zbl 1057.05044)]
• Counting connected graphs asymptotically
• Counting connected graphs inside-out
• FORMULAE FOR THE NUMBER OF SPARSELY-EDGED STRONG LABELLED DIGRAPHS
• How frequently is a system of 2-linear Boolean equations solvable?
• On Some Features of the Structure of a Random Graph Near a Critical Point
• On the number of sparse connected graphs
• Random 2-XORSAT at the Satisfiability Threshold
• The Evolution of Random Graphs
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• The asymptotic number of labeled graphs with given degree sequences
• The birth of the giant component
• The critical behavior of random digraphs
• The number of connected sparsely edged graphs
• The number of connected sparsely edged graphs. III. Asymptotic results
• The transitive closure of a random digraph

Cited in

(5)

• Counting strongly connected \((k_1,k_2)\)-directed cores
• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
• Asymptotic enumeration of strongly connected digraphs by vertices and edges
• The critical window in random digraphs
• Birth of a giant \((k_{1},k_{2})\)-core in the random digraph

This page was built for publication: Counting strongly-connected, moderately sparse directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2844082)