一些图的弱外部平衡划分

Weak External Bisection of Some Graphs

摘要: 设G是一个图。G的一个2-划分是V(G)的一个2-划分，即V(G)=V₁∪V₂且V₁∩V₂= ∅。如果一个2-划分满足||V₁|-|V₂||≤1，我们就称其为平衡划分。本文的研究主要基于Bollobás和Scott提出的一个猜想：每个图G都有一个平衡划分(V₁,V₂)，对于V₁中的每一个顶点v，v的邻点中至少有一半减去一个在V₂中；对于V₂中的每一个顶点v，v的邻点中至少有一半减去一个在V₁中。在本文中，将对二部图、皇冠图以及风车图证实这一猜想。

Abstract: Let G be a graph. A bipartition of G is a bipartition of V(G) with V(G)=V₁∪V₂ and V₁∩V₂= ∅. If a bipartition satisfies ||V₁|-|V₂||≤1, we call it a bisection. The research in this paper is mainly based on a conjecture proposed by Bollobás and Scott: every graph G has a bisection (V₁,V₂) such that ∀v∈V₁, at least half minus one of the neighbors of v are in the V₂;∀v∈V₂, at least half minus one of the neighbors of v are in the V1. In this paper, we confirm this conjecture for some bipartite graphs, crown graphs and windmill graphs.