The antibandwidth problem is to label vertices of a graph G(V,E) bijectively by integers 0,1,.,|V|-1 in such a way that the minimal difference of labels of adjacent vertices is maximized. In this paper we study the antibandwidth of Hamming graphs. We provide labeling algorithms and tight upper bounds for general Hamming graphs Πk=1dKnk. We have exact values for special choices of ni′s and equality between antibandwidth and cyclic antibandwidth values. Moreover, in the case where the two largest sizes of ni′s are different we show that the Hamming graph is multiplicative in the sense of [9]. As a consequence, we obtain exact values for the antibandwidth of p isolated copies of this type of Hamming graphs.
展开▼
机译：反带宽问题是以这样的方式用整数0,1，。，| V | -1双射地标记图G（V，E）的顶点，使得相邻顶点的标记的最小差异最大。在本文中，我们研究了汉明图的抗带宽。我们为一般汉明图Πk= 1dKnk提供了标注算法和严格的上限。对于ni的特殊选择以及反带宽和循环反带宽值之间的相等性，我们有确切的值。此外，在ni的两个最大大小不同的情况下，我们表明汉明图在[9]的意义上是可乘的。结果，我们获得了此类汉明图的p个独立副本的抗带宽的精确值。
展开▼
