[1]颜 娟.(k,k-1)-双正则图的平衡Judicious Partitions(英文)[J].南京师大学报(自然科学版),2008,31(03):24-28.
　Yan Juan,Xu Baogang.Balanced Judicious Partitions of (k,k-1)-Biregular Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2008,31(03):24-28.
点击复制

(k,k-1)-双正则图的平衡Judicious Partitions(英文)()
分享到：

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

卷:
第31卷
期数:
2008年03期
页码:
24-28
栏目:
数学
出版日期:
2008-09-30

文章信息/Info

Title:
Balanced Judicious Partitions of (k,k-1)-Biregular Graphs
作者:
颜 娟1;  2;  许宝刚1
( 1. 南京师范大学数学与计算机科学学院, 江苏南京, 210097)
( 2. 新疆大学数学与系统科学学院, 新疆乌鲁木齐, 830046)
Author(s):
Yan Juan1; 2; Xu Baogang1
( 1. School ofMathem atics and Com puter S cien ce, Nan jing Norm alUn iversity, Nan jing 210097, Ch ina)
( 2. C ollege ofM athem atics and System S cien ces, X in jiang Un iversity, U lmoq i830046, Ch ina)
关键词:
judicious partition;  平衡二部划分;  (k;  k-1)-双正则图
Keywords:
judic ious pa rtition;  ba lanced bipartition;  ( k;  k- 1) - b iregu lar g raph
分类号:
O157.5
摘要:
Bollobás和Scott提出猜想:任意一个边数为m且最小度大于1的图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数不超过m/3.Bollobás和Scott证明了绝大部分正则图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数比m/4小.这里讨论(k,k-1)-双正则图的平衡二部划分,证明了每一个(k,k-1)-双正则图存在平衡二部划分使得每一部分点集的导出子图包含的边数是m/4左右.
Abstract:
Bo llobás and Sco tt conjectured that: eve ry graph w ith m edges and m in imum degree at least 2 has a ba lanced b ipartition w ith at mo stm /3 edg es in each v ertex class. They proved that m ost regular g raphs have a balanced partitions w ith less than m /4 edges in each vertex c lass. In th is paper, balanced b ipartitions o f ( k, k- 1)-biregu la r g raphs were considered, and it w as proved tha t every ( k, k- 1)-b iregu lar g raph adm its a balanced b ipartition w ith aboutm /4 edges in each vertex class.

参考文献/References:

[ 1]  Bo llobás B, Sco tt A D. Judicious partitions o f graph[ J] . Per iodM ath H ung ar, 1993, 26( 2) : 125-137.
[ 2]  Bo llobás B, Sco tt A D. Exact bounds for judicious partitions o f graphs[ J]. Com b ina torica, 1999, 19( 4): 473-486.
[ 3]  Bo llobás B, Sco tt A D. Judicious partitions o f bounded-degree graphs[ J]. J Graph Theory, 2004, 46( 2) : 131-143.
[ 4]  Bo llobás B, Sco tt A D. Prob lem s and results on jud ic ious partitions[ J]. Random Struct A lg, 2002, 21( 3 /4): 414-430.

备注/Memo

备注/Memo:
Foundation item: Supported by NSFC( 10671095) .
Corresponding autho r: Y an Ju an, doctoral cand idate, m ajored in graph theory. E-mail:yan juan207@ sohu. com
更新日期/Last Update: 2013-05-05