Antibandwidth of d-Dimensional Meshes

摘要

The antibandwidth problem is to label vertices of a graph G = (V, E) bijectively by 0,1, 2,,..., | V| - 1 such that the minimal difference of labels of adjacent vertices is maximised. In this paper we discuss the antibandwidth of d-dimensional meshes. We provide labelling algorithm giving antibandwidth value matching the upper bound up to the third order term. This work is a continuation of our previous results for antibandwidths of two and three-dimensional meshes and hypercubes.