Ömer Egecioglu and Cemil M. Azizoglu
The Edge-isoperimetric Number of Generalized Cylinders
Abstract.
Abstract: A d-dimensional generalized cylinder G^d is the Cartesian product
of d graphs, each of which is a
path graph or a cycle graph. We use an embedding technique to show that the
edge-isoperimetric number i(G^d)
is given by i(G^d) = min {i(P_k), i(C_l)} where P_k and C_l are the
largest path graph and the largest
cycle graph among the factors in G^d, and the factor on the right achieving the
minimum value has an even number
of vertices. As a byproduct, we obtain the isoperimetric number of
multidimensional even tori (product of cycle graphs
on even number of vertices) and multidimensional even arrays (product of path
graphs on even number of vertices). In
fact for tori and arrays, our result only requires the size of the largest factor
to be even. We also obtain a complete
description of the corresponding isoperimetric sets as well as exact formulas for
the bisection width of these
generalized cylinders.
Keywords: Generalized cylinder, product graph, array, torus, isoperimetric number,
bisection width, edge separator.
omer@cs.ucsb.edu