The Edge-isoperimetric Number of Generalized Cylinders

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 embeddingtechnique 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 largestpath graph and the largest cycle graph among the factors in $G^d$, and thefactor on the right achieving the minimum value has an even number ofvertices. As a byproduct, we obtain the isoperimetric number ofmultidimensional even tori (product of cycle graphs on even number of vertices)and multidimensional even arrays (product of path graphs on even number ofvertices). In fact for tori and arrays, our result only requires the size ofthe largest factor to be even. We also obtain a complete description of thecorresponding isoperimetric sets as well as exact formulas for the bisectionwidth of these generalized cylinders.