On the bandwidth of 3-dimensional Hamming graphs

J. Balogh, S. L. Bezrukov, L. H. Harper, A. Seress

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)488-495
Number of pages8
JournalTheoretical Computer Science
Issue number1-3
StatePublished - Nov 6 2008


  • Combinatorial optimization

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the bandwidth of 3-dimensional Hamming graphs'. Together they form a unique fingerprint.

Cite this