Antibandwidth and cyclic antibandwidth of Hamming graphs

The antibandwidth problem is to label vertices of a graph G(V,E)G(V,E) bijectively by integers 0,1,…,|V|−10,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 pp isolated copies of this type of Hamming graphs.