|Table of Contents|

Balanced Judicious Partitions of (k,k-1)-Biregular Graphs(PDF)

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

Issue:
2008年03期
Page:
24-28
Research Field:
数学
Publishing date:

Info

Title:
Balanced Judicious Partitions of (k,k-1)-Biregular Graphs
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)
Keywords:
judic ious pa rtition;  ba lanced bipartition;  ( k;  k- 1) - b iregu lar g raph
PACS:
O157.5
DOI:
-
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:
-
Last Update: 2013-05-05