On the bandwidth of 3-dimensional Hamming graphs

AbstractThis paper presents strategies for improving the known upper and lower bounds for the bandwidth of Hamming graphs (Kn)d and [0,1]d. Our labeling strategy lowers the upper bound on the bandwidth of the continuous Hamming graph, [0,1]3, from .5 to .4497. A lower bound of .4439 on bw([0,1]3) follows from known isoperimetric inequalities and a related dynamic program is conjectured to raise that lower bound to 4/9=.4444…. In particular, showing the power of our method, we prove that the bandwidth of K6×K6×K6 is exactly 101