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

• 作者: 李光暖 许宝刚
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 平衡划分 逆平衡划分 正则图
• 年，卷（期）: 2009,（3）
• 页码范围: 353-358
• 页数: 6页
• 分类号: O157.5
• 字数: 4928字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2009.03.015

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许宝刚	南京师范大学数学与计算机科学学院	11	16	2.0	3.0
2	李光暖	南京师范大学数学与计算机科学学院	1	3	1.0	1.0