Author(s)

Yumin Liu^1,2

¹Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, China.
²Department of Mathematics, Lishui University, Lishui, China.

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. The conjecture is that every graph G has a bisection (V₁, V₂) such that ∀v ∈ V₁, at least half minuses one of the neighbors of v are in the V₂; ∀v ∈ V₂, at least half minuses one of the neighbors of v are in the V₁. In this paper, we confirm this conjecture for some bipartite graphs, crown graphs and windmill graphs.

Weak External Bisection, Bipartite Graph, Windmill Graph

Liu, Y. (2024) Weak External Bisection of Some Graphs. Journal of Applied Mathematics and Physics, 12, 91-97. doi: 10.4236/jamp.2024.121009.