Abstract
Extremal Sets Minimizing Dimension-normalized Boundaryin Hamming Graphs
by: M. Cemil Azizoglu and Omer Egecioglu
Abstract:
We prove that the set of first m vertices of a Hamming graphin reverse-lexicographic order constitutes an extremal set minimizing the dimension-normalized edge-boundary over all m-vertex subsets of the graph. This generalizes a result of Lindsey and can be used to prove a tight lower bound for the isoperimetric number and the bisection width of arrays.
Keywords:
Hamming graph, product graph, array, isoperimetric number,bisection width, extremal set.
Date:
June 2000
Document: 2000-11
