Weak External Bisections of Regular Graphs.

Yan, Juan; Chen, Ya-Hong

Let G be a graph. A bisection of G is a bipartition of V(G) with V (G) = V 1 ∪ V 2 , V 1 ∩ V 2 = ∅ and | | V 1 | - | V 2 | | ≤ 1 . Bollobás and Scott conjectured that every graph admits a bisection such that for every vertex, its external degree is greater than or equal to its internal degree minus one. In this paper, we confirm this conjecture for some regular graphs. Our results extend a result given by Ban and Linial (J Graph Theory 83:5–18, 2016). We also give an upper bound of the maximum bisection of graphs.

Graphs & Combinatorics, 2024, Vol 40, Issue 3, p1

0911-0119

Academic Journal

10.1007/s00373-024-02796-3