Asymptotic enumeration of sparse graphs with a minimum degree constraint

DOI10.1016/S0097-3165(02)00017-1zbMath1017.05051MaRDI QIDQ1869761

Nicholas C. Wormald, Boris G. Pittel

Publication date: 28 April 2003

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Asymptotic enumeration (05A16)

Related Items

Phase transitions in the edge/concurrent vertex model, Counting sparse \(k\)-edge-connected hypergraphs with given number of vertices and edges, Sandwiching a densest subgraph by consecutive cores, Orientability Thresholds for Random Hypergraphs, Local Limit Theorems for the Giant Component of Random Hypergraphs, Cores of random \(r\)-partite hypergraphs, Corrigendum to ``Counting connected graphs inside-out [J. Comb. Theory, Ser. B 93, No. 2, 127--172 (2005; Zbl 1057.05044)], The Firstk-Regular Subgraph is Large, Counting connected graphs inside-out, On the robustness of random \(k\)-cores, Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs, Counting strongly-connected, moderately sparse directed graphs, Asymptotic enumeration of strongly connected digraphs by vertices and edges, Asymptotic enumeration of sparse 2-connected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• The asymptotic number of labeled graphs with \(n\) vertices, \(q\) edges, and no isolated vertices
• On the number of graphs with a fixed number of vertices, edges, and isolated vertices
• Sudden emergence of a giant \(k\)-core in a random graph
• Central and local limit theorems applied to asymptotic enumeration
• On the strength of connectedness of a random graph
• Paths in a random digital tree: limiting distributions
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• A Graph-Valued Markov Process as Rings-Allowed Polymerization Model: Subcritical Behavior