Counting connected graphs with large excess

MaRDI QIDQ5111023zbMATH OpenFDO

Authors Elie de Panafieu

Publication date 26 May 2020

Full work available at URL https://arxiv.org/abs/1604.07307, https://dmtcs.episciences.org/6368

zbMATH Keywords

asymptotic expansiongenerating functionsanalytic combinatoricsconnected graphs

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Connectivity (05C40)

Abstract: We enumerate the connected graphs that contain a linear number of edges with respect to the number of vertices. So far, only the first term of the asymptotics was known. Using analytic combinatorics, i.e. generating function manipulations, we derive the complete asymptotic expansion.

Recommendations

• Analytic combinatorics of connected graphs
• Airy phenomena and analytic combinatorics of connected graphs
• Counting connected graphs asymptotically
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• Counting dense connected 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 1111371 (Why is no real title available?)
• Airy phenomena and analytic combinatorics of connected graphs
• Analytic combinatorics
• Analytic combinatorics in several variables.
• Counting connected graphs asymptotically
• Counting connected graphs inside-out
• Multivariate asymptotics for products of large powers with applications to Lagrange inversion
• On the number of sparse connected graphs
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• The birth of the giant component
• The first cycles in an evolving graph
• Threshold functions for small subgraphs in simple graphs and multigraphs

Cited in

(7)

• Airy phenomena and analytic combinatorics of connected graphs
• Forbidden subgraphs in connected graphs
• Counting connected graphs asymptotically
• Counting enriched multigraphs according to the number of their edges (or arcs)
• Analytic combinatorics of connected graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Counting connected graphs inside-out

This page was built for publication: Counting connected graphs with large excess

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