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

Some results of regular graphs on the existence of balanced partition

作　　者：李光暖[1] 许宝刚[1] 

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

出　　处：《高校应用数学学报（A辑）》2009年第3期353-358,共6页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(10671095)

摘　　要：一个图G的划分V(G)=V_1∪V2,如果满足下列条件:(1)||V_1|—|V_2||≤1; (2)任给v∈V(G),当v∈V_1时,满足d_(G[v_1])(v)-d_(G[v_2∪{v}])(v)≤1;当v∈V_2时,满足d_(G[K])(v)-d_(G[v_1∪{v})(v)≤1.则称V(G)=V_1∪V_2为G的一个平衡划分.Bollob(?)s与Scott猜想任一图都存在平衡划分.文中证明了k-正则图存在平衡划分,其中k∈{3,n-1,n-2,n-3,n-4}.对于k=3或n-4的一个特殊情形,还给出了寻找k-正则图平衡划分的算法.A bipartition V（G）=V1∪V2 of a graph G is called a balanced partition if （1）｜｜V1｜｜-｜｜V2｜｜≤1; （2） de[V1]（v） - dG[V2∪{v}]（v）≤1, for all v∈V1, and dG[v2]（v） - dG[V1∪{v}]（v）≤1, for all v∈V2. Bollobas and Scott conjectured that every graph has a balanced partition. In this paper, it is proved that every k-regular graph admits a balanced partition, where k∈{3, n - 1, n - 2, n - 3, n - 4）. For k=3 or a special case of n - 4, algorithms are presented for searching a balanced partition in k-regular graphs.

关 键 词：平衡划分 逆平衡划分 正则图 

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