DECOMPOSITION OF RANDOM GRAPHS INTO COMPLETE BIPARTITE GRAPHS

被引：5
|
作者：
Chung, Fan [1 ]
Peng, Xing [2 ]
机构：
[1] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA
[2] Tianjin Univ, Ctr Appl Math, Tianjin 300072, Peoples R China
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 2016年 / 30卷 / 01期
关键词：
random graphs; decomposition; bipartition number; GRAHAM-POLLAK THEOREM; PROOF;
D O I：
10.1137/140960888
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We consider the problem of partitioning the edge set of a graph G into the minimum number tau(G) of edge-disjoint complete bipartite subgraphs. We show that for a random graph G in G(n, p), where p is a constant no greater than 1/2, asymptotically almost surely tau(G) is between n - c(log(1/p) n)(3+is an element of) and n - (2 + o(1)) log(1/(1-p)) n for any positive constants c and is an element of.
引用
收藏
页码：296 / 310
页数：15
相关论文
共 50 条
12345