On the Bandwidth of a Product of Complete Graphs

by Appelt, Eric Andrew

Abstract (Summary)
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.
Bibliographical Information:


School:Miami University

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

© 2009 All Rights Reserved.