最大度与最小度相差不超过2的图的平衡judicious划分  

Balanced judicious partitions of graphs with △(G)-δ(G)≤2

作　　者：胡晓臣 何卫力[1] 郝荣霞[1] 

机构地区：[1]北京交通大学理学院,北京100044

出　　处：《运筹学学报》2015年第1期108-116,共9页Operations Research Transactions

基　　金：国家自然科学基金(No.11371052)

摘　　要：图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.A bipartition V1 and V2 of V（G） of a graph G is balanced if ｜｜V1｜-｜V2｜｜ ≤ 1.Bollobas and Scott conjectured that every graph with m edges and minimum degree at least 2 admits a balanced bipartition V1,V2 such that max{e（V1）,e（V2）} ≤ m/3,where e（Vi） denoted the number of edges of G with both ends in Vi（i = 1,2）.They showed that this conjecture held for regular graphs（i.e.,when △（G） = δ（G））.Yan Juan and Xu Baogang showed that every（k,k-1）-biregular graph（i.e.,△（G）-δ（G） ≤ 1） admitted a balanced bipartition into V1,V2 with about m/4 edges in each vertex class.In this paper we extend this result to graphs with △（G）- δ（G） ≤ 2.

关 键 词：judicious划分 平衡二部划分 最大度 最小度 

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