ALCOMFT-TR-02-97

Sergei Bezrukov and Robert Elsässer
Edge-Isoperimetric Problems for Cartesian Powers of Regular Graphs
Paderborn. Work package 2. May 2002.

Abstract: We consider an edge-isoperimetric problem (EIP) on the cartesian powers of graphs. One of our objectives is to extend the list of graphs for whose cartesian powers the lexicographic order provides nested solutions for the EIP. We present several new classes of such graphs that include as special cases all presently known graphs with this property. Our new results are applied to derive best possible edge-isoperimetric inequalities for the cartesian powers of arbitrary regular, resp. regular bipartite graphs with a high density.

Postscript file: ALCOMFT-TR-02-97.ps.gz (116 kb).