On the connectivity of random graphs from addable classes
On the connectivity of random graphs from addable classes
复制标题
关于可添加类的随机图的连通性
DOI：
10.1016/j.jctb.2012.12.001
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
K. Panagiotou
中科院分区：
文献类型：
--
作者：
M. Kang;K. Panagiotou
一类图A称为弱可加图（或桥可加图），如果对任意G∈A和G中的任意两个不同分支C1和C2，在C1和C2之间加一条边得到的任意图也在A中. McDiarmid，Steger and Welsh（2006）在[6]中证明了当n→∞时，从弱可加图A中的所有n个顶点的图中随机一致选择的图，其连通概率至少为e−1/2+o（1）。在本文中，我们证明了该猜想是正确的，在一个更强的假设。一类图G称为桥可变图，如果对任意G∈G和G中的任意桥e，G∈G当且仅当G−e∈G。本文证明了当n→∞时，从可变桥图G中的所有n阶图中随机一致选取的图，其连通概率至少为e−1/2+o（1）.在我们的分析中的主要工具是一个紧密的枚举结果，解决了一个给定的森林可以补充到一个森林与较少的组件的方式的数量。
A class A of graphs is called weakly addable (or bridge-addable) if for any G∈A and any two distinct components C1and C2in G, any graph that can be obtained by adding an edge between C1and C2is also in A. McDiarmid, Steger and Welsh (2006) conjectured in [6] that a graph chosen uniformly at random among all graphs with n vertices in a weakly addable A is connected with probability at least e−1/2+o(1), as n→∞. In this paper we show that the conjecture is true under a stronger assumption. A class G of graphs is called bridge-alterable, if for any G∈G and any bridge e in G, G∈G if and only if G−e∈G. We prove that a graph chosen uniformly at random among all graphs with n vertices in a bridge-alterable G is connected with probability at least e−1/2+o(1), as n→∞. The main tool in our analysis is a tight enumeration result that addresses the number of ways in which a given forest can be complemented to a forest with fewer components.
可添加单调图类的连通性
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
L. Addario;C. McDiarmid;B. Reed
通讯作者：
B. Reed
可添加图形类的连接性
DOI：
--
发表时间：
2008
期刊：
J. Comb. Theory B
影响因子：
--
作者：
P. Balister;B. Bollobás;S. Gerke
通讯作者：
S. Gerke
来自平面和其他可添加类的随机图
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
C. McDiarmid;A. Steger;D. Welsh
通讯作者：
D. Welsh