English

运筹学学报 ›› 2015, Vol. 19 ›› Issue (1): 108-116.

• 运筹学 • 上一篇    下一篇

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

胡晓臣1, 何卫力1, 郝荣霞1,*   

  1. 1. 北京交通大学理学院, 北京 100044
  • 收稿日期:2014-07-18 出版日期:2015-03-15 发布日期:2015-03-15
  • 通讯作者: 郝荣霞 E-mail:rxhao@bjtu.edu.cn
  • 基金资助:

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

Balanced judicious partitions of graphs with $\Delta($G$)-\delta($G$)\leq$2

HU Xiaochen1, HE Weili1, HAO Rongxia1,*   

  1. 1. School of Science, Beijingjiaotong University, Beijing 100044, China
  • Received:2014-07-18 Online:2015-03-15 Published:2015-03-15

PDF

753

摘要： 图$G$的顶点集$V(G)$的一个二部划分$V_{1}$和$V_{2}$叫做平衡二部划分, 如果$||V_{1}|-|V_{2}||\leq1$ 成立. Bollob\'{a}s和Scott猜想: 每一个有$m$条边且最小度不小于2的图, 都存在一个平衡二部划分$V_{1}$, $V_{2}$, 使得{\rm max}$\{e(V_{1}), e(V_{2})\}\leq\frac{m}{3}$, 此处$e(V_{i})$ 表示两顶点都在$V_{i}(i=1, 2)$ 中的边的条数. 他们证明了这个猜想对正则图(即$\Delta(G)=\delta(G)$)成立. 颜娟和许宝刚证明了每个($k$, $k-1$)-双正则图(即$\Delta(G)-\delta(G)\leq1$)存在一个平衡二部划分$V_{1}$, $V_{2}$,  使得每一顶点集的导出子图包含大约$\frac{m}{4}$ 条边. 这里把该结论推广到最大度和最小度相差不超过 2 的图 $G$.

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

Abstract: A bipartition $V_{1}$ and $V_{2}$ of $V(G)$ of a graph $G$ is balanced if $||V_{1}|-|V_{2}||\leq1$. Bollob\'{a}s and Scott conjectured that every graph with $m$ edges and minimum degree at least 2 admits a balanced bipartition $V_{1}$, $V_{2}$ such that {\rm max}$\{e(V_{1}), e(V_{2})\}\leq\frac{m}{3}$, where $e(V_{i})$ denoted the number of edges of $G$ with both ends in $V_{i}(i=1, 2)$. They showed that this conjecture held for regular graphs(i.e., when $\Delta(G)=\delta(G)$). Yan Juan and Xu Baogang showed that every ($k$, $k-1$)-biregular graph(i.e., $\Delta(G)-\delta(G)\leq1$) admitted a balanced bipartition into $V_{1}$, $V_{2}$ with about $\frac{m}{4}$ edges in each vertex class. In this paper we extend this result to graphs with $\Delta($G$)-\delta($G$)\leq2$.

Key words: judicious bipartition, balanced bipartition, maximum degree, minimum degree

中图分类号: