二部平衡公平划分的一个下界  

A Lower Bound on Judicious Balanced Bipartition Problem of Graphs

作　　者：李海燕[1] 许宝刚[2] 

机构地区：[1]南京师范大学数学科学学院,南京210023 [2]南京师范大学数学科学学院数学研究所,南京210023

出　　处：《数学学报（中文版）》2013年第5期651-660,共10页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金资助项目(10931003;11171160);教育部博士点基金

摘　　要：设V_1,V_2是图G的一个二部划分.如果一1≤|V_1|-|V_2|≤1,则称V_1,V_2是G的一个二部平衡划分.对于n个顶点m条边的简单图G,本文证明了:(1)若G是k-正则图(k≥3),则G存在一个最小二部平衡划分V_1,V_2,使得max{e(V_1),e(V_2)}≥((k-1)m)/4k;(2)如果r是大于4的实数,且当n是偶数时△(G)≤((3r-4))/(r+4)δ(G)-(2r)/(r+4),当n是奇数时△(G)≤(3r-4)/(r+4)δ(G)-(8r)/(r+4),那么G存在一个二部平衡划分,使得min{e(V_1),e(V_2)}≥m/r,这里e(V_i)表示G中两个顶点都在V_i中的边的数目.A balanced bipartition of a graph G is a bipartition V1 and V2 of V（G） such that -1≤｜V1｜—｜V2｜ 1.Let G be a graph with n vertices and m edges, and let r be a real number greater than 4.In this paper,it is proved that：（1） G admits a minimum balanced bipartition V_1,V_2 such that max{e（V1）,e（V2）}≥（（k-1）m）/4k if it is k-regular with k≥3;and（2） G admits a minimum balanced bipartition such that mm{e{V_1）,e{V_2）} m/r provided that△（G）≤（3r-4）/r＋4δ{G） -2r/r＋4 if n is even,and△（G）≤3r-4/r＋4δ（G） -8r/r＋4 if n is odd,where e（V_i） denotes the number of edges of G with both ends in Vi.

关 键 词：平衡二部划分 下界 图 

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