数学科学系

Department of Mathematical Sciences

On Judicious Bisections of Graphs

报告题目:On Judicious Bisections of Graphs

 

报告人:Prof. Xingxing Yu (Georgia Institute of Technology)

 

时间:2013年6月6日(星期四)16:00--17:00

 

地点:理科楼数学系A304

 

摘要:A bisection of a graph G is a bipartition $S_1,S_2$ of V(G) such that $||S_1|-|S_2||\le 1$. It is NP-hard to find a bisection $S_1,S_2$ maximizing $e(S_1,S_2)$ (repectively, minimizing $\max\{e(S_1),e(S_2)\}$), where $e(S_1,S_2)$ denotes the number of edges from $S_1$ to $S_2$, and $e(S_i)$ denotes the number of edges of $G$ with both ends in $S_i$. There has been extensive research on bisections from algorithmic point of view, but very few extremal results are known. Bollob\'{a}s and Scott conjectured that if $G$ is a graph with $m$ edges and minimum degree at least $2$ then $G$ admits a bisection $S_1,S_2$ such that $e(S_i)\le m/3$ for $i=1,2$. In this paper, we confirm this conjecture and show that any extremal graph is a disjoint union of triangles. Joint work with Baogang Xu.

 

联系人:陆玫