Counting connected graphs asymptotically

DOI10.1016/J.EJC.2006.05.006MaRDI QIDQ850082zbMATH OpenOpenAlexFDO

Authors Remco van der Hofstad, Joel Spencer

Publication date 15 November 2006

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial probability (60C05) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We find the asymptotic number of connected graphs with $k$ vertices and $k-1+l$ edges when $k,l$ approach infinity, reproving a result of Bender, Canfield and McKay. We use the {em probabilistic method}, analyzing breadth-first search on the random graph $G(k,p)$ for an appropriate edge probability $p$. Central is analysis of a random walk with fixed beginning and end which is tilted to the left.

Recommendations

• Counting connected graphs with large excess
• Analytic combinatorics of connected graphs
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• Enumerating graphs and Brownian motion
• Counting connected graphs and hypergraphs via the probabilistic method

Cites work

• scientific article; zbMATH DE number 3151315 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Counting connected graphs inside-out
• On the number of sparse connected graphs
• The Brownian excursion area: A numerical analysis
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• The number of connected sparsely edged graphs
• The number of connected sparsely edged graphs. III. Asymptotic results

Cited in

(18)

• scientific article; zbMATH DE number 6813595 (Why is no real title available?)
• Airy phenomena and analytic combinatorics of connected graphs
• Counting connected graphs with large excess
• Another proof of Wright's inequalities
• scientific article; zbMATH DE number 4075100 (Why is no real title available?)
• Brownian approximation to counting graphs
• Counting enriched multigraphs according to the number of their edges (or arcs)
• Birth and growth of multicyclic components in random hypergraphs
• 2-Xor revisited: satisfiability and probabilities of functions
• Analytic combinatorics of connected graphs
• Local limit theorems for the giant component of random hypergraphs
• The order of the giant component of random hypergraphs
• The probability of unusually large components in the near-critical Erdős-Rényi graph
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 1552347 (Why is no real title available?)
• The asymptotic number of connected \(d\)-uniform hypergraphs
• Counting connected graphs inside-out
• Counting strongly-connected, moderately sparse directed graphs

This page was built for publication: Counting connected graphs asymptotically

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