Operations Research Transactions ›› 2015, Vol. 19 ›› Issue (1): 108-116.

• Original Articles • Previous Articles     Next Articles

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

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

CLC Number: