Note on the bisection width of cubic graphs

Abstract The bisection width is the minimum number of edges required to split the vertex set of a graph into two (nearly) equal parts. Monien and Preis proved that the bisection width of a cubic graph with n nodes is bounded above by n ∕ 6 + o ( n ) . Here we show that every cubic graph of even order n ≥ 16 has bisection width less than n ∕ 2 , thus these graphs violate the even cut condition (ECC). All edge-minimal subcubic graphs satisfying ECC are also described. The bisection width is a reference parameter to compare networks for parallel architectures; ECC is a property necessary for bottleneck free all-to-all communications.