Optimal Numberings of an $N \times N$ Array
Graeme Mitchison, Richard M. Durbin · SIAM Journal on Algebraic and Discrete Methods · 1986
Given a numbering of the vertices of a graph, one can define the edgesum [6] as the sum of differences between adjacent vertices. The problem of finding numberings which are optimal in the sense of minimizing the edgesum is NP-complete [2] but has been solved in the special case where the graph is the $2^n $ cube [3] and for several instances of graphs with high degrees of symmetry [6]. We find the solutions for numberings of an $N \times N$ array. These have practical application in the problem of representing spatial information in a one-dimensional medium. To find our solutions, we exploit the fact that such numberings can always be taken to be ordered, in the sense that numbers increase along rows and down columns. We also consider a generalization of this problem to the case where the differences are raised to a power q. We derive bounds on the edgesum in this case, and show that the optimal numberings for $q < 1$ must be essentially different from those we have found for $q = 1$. While the latter may be assumed to be ordered, and have regions of numbering by rows or columns, neither statement is true for the case $q < 1$. We hypothesize that the solution in this case has a fractal character.