Abstract
The Isoperimetric Number of d-dimensional k-ary Arrays
by: M. Cemil Azizoglu and Omer Egecioglu
Abstract:
The d-dimensional k-ary array $A_k^d$ is the k-fold Cartesian product graph of the path $P_k$ on k vertices. We show that the (edge) isoperimetric number of $A_k^d$ is given by $i(A_k^d)=i(P_k) = {1}/{\\lfloor \\frac{k}{2} \\rfloor}$ for all k and d, and identify the cardinalities and the structure of the isoperimetric sets. For k odd, the cardinalities of the isoperimetric sets are $(k^d -1)/2, (k^d -k)/2, \\ldots ,(k^d-k^{d-1})/2$, whereas every isoperimetric set in $A_k^d$ has cardinality $k^d /2$ when k is even.
Keywords:
Isoperimetric number, multidimensional array, bisection, embedding, linear layout, lower bound.
Date:
September 1998
Document: 1998-24
