关于正则图存在平衡划分的一些结果

• 作 者: 李光暖 许宝刚
• 机 构: 南京师范大学数学与计算机科学学院
• 出 处: 高校应用数学学报：A辑
• 发表日期: 2009年3期
• 关键词: 平衡划分 逆平衡划分 正则图 balanced partition opposite balanced partition： regular graph
• 基金项目: 国家自然科学基金（10671095）

一个图G的划分V（G）=V1∪V2，如果满足下列条件：（1）｜｜V1｜｜-｜｜V2｜｜≤1；（2）任给v∈V（G），当v∈V1时，满足dG[V1]（v）-dG[V2∪{v}]（v）≤1；当v∈V2时，满足dG[V2]（v）-dG{V1{v}}≤1。则称V（G）=V1∪V2为G的一个平衡划分．Bollobas与Scott猜想任一图都存在平衡划分．文中证明了k-正则图存在平衡划分，其中k∈{3，n-1，n-2，n-3，n-4}．对于k=3或n-4的一个特殊情形，还给出了寻找k-正则图平衡划分的算法．