Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph
Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph
复制标题
按度数序列对图进行渐近枚举，以及随机图的度数序列
DOI：
10.4171/jems/1355
复制
发表时间：
2017
影响因子：
2.6
通讯作者：
N. Wormald
中科院分区：
文献类型：
--
作者：
Anita Liebenau;N. Wormald
本文将随机图的一个基本参数--度序列与一个简单的近独立二项随机变量模型联系起来。这证实了1997年的一个猜想。因此，图的度的联合分布的许多有趣的函数，例如中位度的分布，变得易于估计。我们的结果是通过证明1990年猜想的具有给定度序列的图的个数的渐近公式而建立的。特别地，这给出了所有$d$的$d$-正则图的个数的渐近公式。
In this paper we relate a fundamental parameter of a random graph, its degree sequence, to a simple model of nearly independent binomial random variables. This confirms a conjecture made in 1997. As a result, many interesting functions of the joint distribution of graph degrees, such as the distribution of the median degree, become amenable to estimation. Our result is established by proving an asymptotic formula conjectured in 1990 for the number of graphs with given degree sequence. In particular, this gives an asymptotic formula for the number of $d$-regular graphs for all $d$, as $n\to\infty$.
A·哈贝：（1989）
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--