Counting connected graphs inside-out
Counting connected graphs inside-out
复制标题
从内到外计算连通图
DOI：
10.1016/j.jctb.2004.09.005
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
N. Wormald
中科院分区：
文献类型：
--
作者：
B. Pittel;N. Wormald
这项工作的主题是一个“由内而外”的方法来枚举的图形。它是基于一个著名的分解图到它的2-核心，即最大的子图的最低程度2或以上，和森林的树木重视。使用我们早先的（渐近）公式的总数2-核心与给定数量的顶点和边缘，我们解决了相应的计数问题的连接2-核心。对于参数的子范围，我们还通过使用连接的2-核心的核心的更深的由内而外的概念来枚举那些2-核心。利用这个计数结果，结合Caley的森林公式，我们得到了Bender，坎菲尔德和McKay关于n点m边连通图个数的渐近公式的一个替代的、简单的证明，并改进了m值范围内的误差估计.作为另一个应用，我们研究了超临界状态下n阶随机图的巨分支的三个参数的极限联合分布，当平均顶点度与1之差远大于n-1/3时.这三个参数是根据巨分支的2-核定义的，即它的最小度为2或更大的最大子图。它们是2-核中的顶点数、2-核的剩余数（边数-顶点数）和不在2-核中的顶点数。我们表明，在整个超临界相的极限分布是联合高斯。特别是，第一次，2-核心的大小被证明是渐近正常的，在尽可能广泛的范围内的平均顶点度。
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 show that 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.