The bisection width of cubic graphs

Authors:

Abstract
For a graph G, define the bisection width bw(G) of G as min { eG(A,B): {A,B} partitions V(G) with ‖A| − |B‖ ≤ 1 } where eG(A, B) denotes the number of edges in G with one end in A and one end in B. We show almost every cubic graph G of order n has bw(G) ≥ n/11 while every such graph has bw(G) ≤ (n + 138)/3. We also show that almost every r-regular graph G of order n has bw(G) ≥ crn where cr → r/4 as r → ∞. Our last result is asymtotically correct.

This publication has 10 references indexed in Scilit: