10.3969/j.issn.1001-4616.2008.03.005
(k,k-1)-双正则图的平衡Judicious Partitions
Bollobás和Scott提出猜想:任意一个边数为m且最小度大于1的图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数不超过m/3.Bollobds和Scott证明了绝大部分正则图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数比m/4小.这里讨论(k,k-1)-双正则图的平衡二部划分,证明了每一个(k,k-1).双正则图存在平衡二部划分使得每一部分点集的导出子图包含的边数是m/4左右.
judicious partition、平衡二部划分、(k、k-1)-双正则图
31
O157.5(代数、数论、组合理论)
NSFC10671095
2008-11-13(万方平台首次上网日期,不代表论文的发表时间)
共5页
24-28