TY - JOUR
T1 - On the bandwidth of 3-dimensional Hamming graphs
AU - Balogh, J.
AU - Bezrukov, S. L.
AU - Harper, L. H.
AU - Seress, A.
N1 - Funding Information:
The first author’s research was funded in part by NSF grants DMS-0302804 DMS-0600303 and DMS-0603769, UIUC Campus Research Board Grants #06139 and #07048 and OTKA grant 049398.
PY - 2008/11/6
Y1 - 2008/11/6
N2 - This 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 b w ([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.
AB - This 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 b w ([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.
KW - Combinatorial optimization
UR - http://www.scopus.com/inward/record.url?scp=53249107535&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=53249107535&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2008.07.029
DO - 10.1016/j.tcs.2008.07.029
M3 - Article
AN - SCOPUS:53249107535
SN - 0304-3975
VL - 407
SP - 488
EP - 495
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-3
ER -