Counting strongly-connected, moderately sparse directed graphs

DOI10.1002/rsa.20433zbMath1270.05059arXiv1005.0327MaRDI QIDQ2844082

Boris G. 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

asymptotics; enumeration; directed graphs; strongly connected

Mathematics Subject Classification ID

05C30: Enumeration in graph theory

05C20: Directed graphs (digraphs), tournaments

05C40: Connectivity

Related Items

The critical window in random digraphs, Birth of a giant \((k_{1},k_{2})\)-core in the random digraph, Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs

Cites Work

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