一些图的弱外部平衡划分  

Weak External Bisection of Some Graphs

作　　者：刘玉敏 

机构地区：[1]浙江理工大学理学院,浙江 杭州 [2]丽水学院数学与计算机学院,浙江 丽水

出　　处：《理论数学》2024年第2期520-526,共7页Pure Mathematics

摘　　要：设G是一个图。G的一个2-划分是V(G)的一个2-划分,即V(G)=V1∪V2且V1∩V2= ∅。如果一个2-划分满足||V1|-|V2||≤1,我们就称其为平衡划分。本文的研究主要基于Bollobás和Scott提出的一个猜想:每个图G都有一个平衡划分(V1,V2),对于V1中的每一个顶点v,v的邻点中至少有一半减去一个在V2中;对于V2中的每一个顶点v,v的邻点中至少有一半减去一个在V1中。在本文中,将对二部图、皇冠图以及风车图证实这一猜想。Let G be a graph. A bipartition of G is a bipartition of V(G) with V(G)=V1∪V2 and V1∩V2= ∅. If a bipartition satisfies ||V1|-|V2||≤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 (V1,V2) such that ∀v∈V1, at least half minus one of the neighbors of v are in the V2;∀v∈V2, 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.

关 键 词：弱外部平衡划分 二部图 皇冠图 风车图 

分 类 号：G63[文化科学—教育学]