The number of steps and the final configuration of relaxation procedures on graphs

This paper considers the relaxation procedure on a graph GG with V(G)={v1,v2,…,vn}V(G)={v1,v2,…,vn}. Initially, a configuration X=(x1,x2,…,xn)X=(x1,x2,…,xn) which is an nn-tuple of real numbers having a positive sum is given. If there is a negative label xixi, then the player can transform XX into X′=(x1′,x2′,…,xn′), where xi′=−xi, xj′=xj+2dixi for each vjvj adjacent to vivi where vivi has exactly didi neighbors, and xk′=xk for all other kk. Wegert and Reiher (Wegert and Reiher (2009)) proved the finiteness of the procedure and proposed the problem of determining graphs for which the final configurations and/or the numbers of steps are unique. In this paper, we give a complete solution to the problem.