Bisections of graphs
Bisections of graphs
复制标题
DOI：
10.1016/j.jctb.2013.06.002
复制
发表时间：
2011-09
期刊：
影响因子：
--
通讯作者：
Choongbum Lee;Po-Shen Loh;B. Sudakov
中科院分区：
文献类型：
--
作者：
Choongbum Lee;Po-Shen Loh;B. Sudakov
图的二分是其顶点集的二分，其中两个部分的顶点数最多相差 1，其大小是穿过两个部分的边的数量。在本文中，受 Bollobás 和 Scott 的几个问题和猜想的启发，我们研究了图的最大二分法。首先，我们将最大割的经典爱德华兹界扩展到二等分。我们的结果的一个简单推论意味着，在 n 个顶点和 m 个边上且没有孤立顶点且最大度数至多为 n/3+1 的每个图都允许大小至少为 m/2+n/6 的二分。然后使用我们开发的扩展爱德华兹界限的工具，我们证明了一个明智的二分结果，该结果表明具有大最小度的图具有二分，其中两个部分跨越相对较少的边。这个一般定理的一个特例回答了 Bollobás 和 Scott 的猜想，并表明在 n 个顶点和 m 个最小度至少为 2 的边上的每个图都允许二分，其中每个部分的边数最多为 (1/3+ o (1)) m。我们还提出了有关图二等分的其他几个结果。
A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and its size is the number of edges which go across the two parts. In this paper, motivated by several questions and conjectures of Bollobás and Scott, we study maximum bisections of graphs. First, we extend the classical Edwards bound on maximum cuts to bisections. A simple corollary of our result implies that every graph on n vertices and m edges with no isolated vertices, and maximum degree at most n/3+ 1, admits a bisection of size at least m/2+ n/6. Then using the tools that we developed to extend Edwardsʼs bound, we prove a judicious bisection result which states that graphs with large minimum degree have a bisection in which both parts span relatively few edges. A special case of this general theorem answers a conjecture of Bollobás and Scott, and shows that every graph on n vertices and m edges of minimum degree at least 2 admits a bisection in which the number of edges in each part is at most (1/3+ o (1)) m. We also present several other results on bisections of graphs.