A special antidilation problem for meshes and Hamming graphs

The antidilation problem consists of a mapping from the set of vertices of the guest graph GG into the set of vertices of the host graph HH such that distance of images of adjacent vertices of GG is maximized in HH. This is a dual problem to the well known dilation problem. In this paper, we study an interesting special case of the antidilation problem when the guest and host graphs are the same. We prove exact results for dd-dimensional meshes, tori and Hamming graphs. In all three cases, the antidilation is very close to radius(H), which is a desired property. As a consequence we solve an open problem of Lagarias about the antidilation of paths in dd-dimensional meshes.