×

On the bandwidth of 3-dimensional Hamming graphs. (English) Zbl 1151.90038

Summary: This paper presents strategies for improving the known upper and lower bounds for the bandwidth of Hamming graphs \((K_n)^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\dots \). In particular, showing the power of our method, we prove that the bandwidth of \(K_{6}\times K_{6}\times K_{6}\) is exactly 101.

MSC:

90C27 Combinatorial optimization
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balogh, J.; Csirik, J. A., Index assignment for two-channel quantization, IEEE Trans. Inform. Theory, 50, 2737-2751 (2004) · Zbl 1284.94042
[2] Balogh, J.; Smyth, C., On the variance of Shannon products of graphs, Discrete Appl. Math., 156, 110-118 (2008) · Zbl 1126.05068
[3] Berger-Wolf, T. Y.; Reingold, E. M., Index assignment for multichannel communication under failure, IEEE Trans. Inform. Theory, 48, 2656-2668 (2002) · Zbl 1062.94500
[4] Chinn, P. Z.; Chvátalová, J.; Dewdney, A. K.; Gibbs, N. E., The bandwidth problem for graphs and matrices — A survey, J. Graph Theory, 6, 223-254 (1982) · Zbl 0494.05057
[5] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman, 338 pp · Zbl 0411.68039
[6] Harper, L. H., Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory, 1, 385-393 (1966) · Zbl 0158.20802
[7] Harper, L. H., On an isoperimetric problem for Hamming graphs, Discrete Appl. Math., 95, 285-309 (1999) · Zbl 0935.05057
[8] Harper, L. H., On the bandwidth of a Hamming graph, Theoret. Comput. Sci., 301, 491-498 (2003) · Zbl 1016.05062
[9] Harper, L. H., (Global Methods for Combinatorial Isoperimetric Problems. Global Methods for Combinatorial Isoperimetric Problems, Cambridge Studies in Advanced Mathematics, vol. 90 (2004), Cambridge Univ. Press), 232 pp · Zbl 1043.05002
[10] Vaishampayan, V. A., Design of multiple description scalar quantizers, IEEE Trans. Inform. Theory, 93, 821-834 (1993) · Zbl 0784.94009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.