Counting connected graphs with large excess

zbMATH Open1440.05117arXiv1604.07307MaRDI QIDQ5111023FDOQ5111023

Elie de Panafieu

Publication date: 26 May 2020

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.

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

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

zbMATH Keywords

asymptotic expansiongenerating functionsanalytic combinatoricsconnected graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

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

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)