On the Periods of Some Graph Transformations
Andrew M. Odlyzko
AT&T Bell Laboratories,
Murray Hill, NJ 07974, USA
Dana J. Randall
AT&T Bell Laboratories,
Murray Hill, NJ 07974, USA
and
Harvard University,
Cambridge, MA 02138, USA
Abstract
For any undirected graph with arbitrary integer values attached to the vertices, simultaneous updates are performed on these values, in which the value of a vertex is moved by one in the direction of the average of the values of the neighboring vertices. (A special rule applies when the value of a vertex equals this average.) It is shown that these transformations always reach a cycle of length one or two. This proves a generalization of a conjecture made by Ghiglia and Mastin in connection with their work on a "phase-unwrapping" algorithm.
