(k,k-1)-双正则图的平衡Judicious Partitions(英文)  

Balanced Judicious Partitions of (k,k-1)-Biregular Graphs

作　　者：颜娟[1] 许宝刚[1] 

机构地区：[1]南京师范大学数学与计算机科学学院

出　　处：《南京师大学报（自然科学版）》2008年第3期24-28,共5页Journal of Nanjing Normal University(Natural Science Edition)

基　　金：NSFC(10671095)

摘　　要：Bollobás和Scott提出猜想:任意一个边数为m且最小度大于1的图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数不超过m/3.Bollobás和Scott证明了绝大部分正则图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数比m/4小.这里讨论(k,k-1)-双正则图的平衡二部划分,证明了每一个(k,k-1)-双正则图存在平衡二部划分使得每一部分点集的导出子图包含的边数是m/4左右.Bolloás and Scott conjectured that：every graph with m edges and minimum degree at least 2 has a balanced bipartition with at most m/3 edges in each vertex class. They proved that most regular graphs have a balanced partitions with less than m/4 edges in each vertex class. In this paper, balanced bipartitions of （ k, k-1） -biregular graphs were considered, and it was proved that every （k,k-1）-biregular graph admits a balanced bipartition with about m/4 edges in each vertex class.

关 键 词：judicious PARTITION 平衡二部划分 (k k-1)-双正则图 

分 类 号：O157.5[理学—数学]