Clique coverings of the edges of a random graph
Clique coverings of the edges of a random graph
复制标题
随机图边缘的团覆盖
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
D. West
中科院分区：
文献类型：
--
作者：
B. Bollobás;P. Erdös;J. Spencer;D. West
随机图（边概率p =1/2）的边可以用O（n2 lnlnn/（lnn）2）个团覆盖.因此，这是随机图的交叉数（也称为团覆盖数）的上界。通过计算参数得到的下限是（1− n）n2/（2lgn）2。
The edges of the random graph (with the edge probabilityp=1/2) can be covered usingO(n2lnlnn/(lnn)2) cliques. Hence this is an upper bound on the intersection number (also called clique cover number) of the random graph. A lower bound, obtained by counting arguments, is (1−ɛ)n2/(2lgn)2.