Counting connected graphs inside-out

Boris Pittel, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

58 Citations (Scopus)

Abstract

The theme of this work is an "inside-out" approach to the enumeration of graphs. It is based on a well-known decomposition of a graph into its 2-core, i.e. the largest subgraph of minimum degree 2 or more, and a forest of trees attached. Using our earlier (asymptotic) formulae for the total number of 2-cores with a given number of vertices and edges, we solve the corresponding enumeration problem for the connected 2-cores. For a subrange of the parameters, we also enumerate those 2-cores by using a deeper inside-out notion of a kernel of a connected 2-core. Using this enumeration result in combination with Caley's formula for forests, we obtain an alternative and simpler proof of the asymptotic formula of Bender, Canfield and McKay for the number of connected graphs with n vertices and m edges, with improved error estimate for a range of m values. As another application, we study the limit joint distribution of three parameters of the giant component of a random graph with n vertices in the supercritical phase, when the difference between average vertex degree and 1 far exceeds n-1/3. The three parameters are defined in terms of the 2-core of the giant component, i.e. its largest subgraph of minimum degree 2 or more. They are the number of vertices in the 2-core, the excess (#edges - #vertices) of the 2-core, and the number of vertices not in the 2-core.We showthat the limit distribution is jointly Gaussian throughout the whole supercritical phase. In particular, for the first time, the 2-core size is shown to be asymptotically normal, in the widest possible range of the average vertex degree.

Original language English 127-172 46 Journal of Combinatorial Theory, Series B 93 2 https://doi.org/10.1016/j.jctb.2004.09.005 Published - Mar 2005 Yes

Keywords

• Asymptotics
• Connected
• Core
• Enumeration
• Graphs
• Limit distributions
• Corrigendum to "Counting connected graphs inside-out"

Pittel, B. & Wormald, N. C., Jul 2008, 98, 4, p. 835-837 3 p.

Research output: Contribution to journalComment / DebateOtherpeer-review

2 Citations (Scopus)