Connectivity of Addable Monotone Graph Classes
Connectivity of Addable Monotone Graph Classes
复制标题
可添加单调图类的连通性
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
B. Reed
中科院分区：
文献类型：
--
作者：
L. Addario;C. McDiarmid;B. Reed
一类标号图A是弱可加的，如果对A中的所有图G和G的不同连通分支中的所有顶点u和v，通过在u和v之间加一条边得到的图也在A中;类A是单调的，如果对G的所有子图H和G的所有G2 A，我们有H2 A.我们证明了，对于任何弱可加的单调类A，其元素的顶点集{1，. . .，n}，则A的一致随机元连通的概率至少为
A class A of labelled graphs is weakly addable if if for all graphs G in A and all vertices u and v in distinct connected components of G, the graph obtained by adding an edge between u and v is also in A; the class A is monotone if for all G 2 A and all subgraphs H of G, we have H 2 A. We show that for any weakly addable, monotone class A whose elements have vertex set {1, . . . , n}, the probability that a uniformly random element of A is connected is at least