ALCOMFT-TR-01-116

Burkhard Monien and Robert Preis
Upper Bounds on the Bisection Width of 3- and 4-regular Graphs
Paderborn. Work package 2. May 2001.

Abstract: We derive new upper bounds on the bisection width of graphs which have a regular vertex degree. We show that the bisection width of large 3-regular graphs with |V| vertices is at most (1/6)*|V|. For the bisection width of large 4-regular graphs we show an upper bound of (2/5)*|V|.

Postscript file: ALCOMFT-TR-01-116.ps.gz (143 kb).