On the Bandwidth of a Product of Complete Graphs
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.
School Location:USA - Ohio
Source Type:Master's Thesis
Keywords:graph bandwidth complete clique hamming weight discrete isoperimetric cartesian product cube compression
Date of Publication:01/01/2003