Int. J. of Foundations of Computer Sci., 10 (3), (1999), pp. 289-300 (in press).
Ömer Egecioglu and Cemil M. Azizoglu
The Isoperimetric Number of d-dimensional k-ary Arrays
Abstract.
The d-dimensional k-ary array A_k^d is the d-fold
Cartesian product graph of the path graph P_k with k vertices.
We show that the (edge) isoperimetric number i(A_k^d) of
A_k^d is given by
$i(A_k^d)=i(P_k) = {1}/{\lfloor \frac{k}{2} \rfloor}$ and
identify the cardinalities and the structure of the isoperimetric
sets.
For odd k, the cardinalities of isoperimetric sets in
A_k^d are
$ \half (k^d -1 ),
\half (k^d -k ), \ldots ,
\half (k^d -k^{d-1})$,
whereas
every isoperimetric set
for k even
has cardinality $ k^d/2$.
omer@cs.ucsb.edu