Abstract
The Bisection Width and the Isoperimetric Number of Arrays
by: M. Cemil Azizoglu and Omer Egecioglu
Abstract:
We prove that the bisection width $bw(A^d)$ of a d-dimensional array$A^d=P_{k_1}\\times P_{k_2} \\times \\cdots\\times P_{k_d}$ where$k_1\\le k_2 \\le \\cdots\\le k_d$, is given by $bw(A^d)=\\sum^d_{i=e} K_i$ wheree is the largest index for which $k_e$ is even(if it exists, e=1 otherwise) and $K_i=k_{i-1} k_{i-2} \\cdots k_1$. Wealso show that the edge-isoperimetric number $i(A^d)$ is given by$i(A^d)=1/\\lfloor{k_d\\over 2}\\rfloor$. Furthermore, a bisectionand an isoperimetric set are constructed.
Keywords:
Product graph, array, isoperimetric number, embedding,bisection width, extremal set.
Date:
November 2000
Document: 2000-12
