On the Bandwidth of a Product of Complete Graphs

by Appelt, Eric Andrew

The purpose of this paper is to discuss the graph bandwidth problem applied to a Cartesian product of complete graphs (Hamming graphs). Consideration is given to general techniques for bounding the bandwidth, as well as the combinatorial method of compression. While the main focus is the exposition of the asymptotically sharp bounds of the general case found by Harper, original results are given concerning a formula for the bandwidth of a cube as well as bounds for a product of two cliques of differing sizes.