The bisection width and the isoperimetric number of arrays Original Research Article

We prove that the bisection width, bw(Ad), of a d-dimensional array Ad=Pk1×Pk2×⋯×Pkd where k1⩽k2⩽⋯⩽kd, is given by bw(Ad)=∑i=edKi where e is the largest index for which ke is even (if it exists, e=1 otherwise) and Ki=ki−1ki−2⋯k1. We also show that the edge-isoperimetric number i(Ad) is given by i(Ad)=1/⌊kd/2⌋. Furthermore, a bisection and an isoperimetric set are constructed.