(k,k-1)-双正则图的平衡Judicious Partitions
Bollobás和Scott提出猜想:任意一个边数为m且最小度大于1的图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数不超过m/3.Bollobds和Scott证明了绝大部分正则图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数比m/4小.这里讨论(k,k-1)-双正则图的平衡二部划分,证明了每一个(k,k-1).双正则图存在平衡二部划分使得每一部分点集的导出子图包含的边数是m/4左右.
作 者： 颜娟 许宝刚 Yan Juan Xu Baogang 作者单位： 颜娟,Yan Juan(南京师范大学数学与计算机科学学院,江苏 南京,210097;新疆大学数学与系统科学学院,新疆,乌鲁木齐,830046)许宝刚,Xu Baogang(南京师范大学数学与计算机科学学院,江苏,南京,210097)
刊 名： 南京师大学报(自然科学版) ISTIC PKU 英文刊名： JOURNAL OF NANJING NORMAL UNIVERSITY(NATURAL SCIENCE EDITION) 年，卷(期)： 2008 31(3) 分类号： O157.5 关键词： judicious partition 平衡二部划分 (k k-1)-双正则图 judicious partition balanced bipartition (k k - 1) - biregular graph