The number of steps and the final configuration of relaxation procedures on graphs
Journal
Discrete Applied Mathematics
Journal Volume
181
Pages
50-53
Date Issued
2015
Author(s)
Abstract
This paper considers the relaxation procedure on a graph G with V(G)={v1,v2,...,vn}. Initially, a configuration X=(x1,x2,...,xn) which is an n-tuple of real numbers having a positive sum is given. If there is a negative label xi, then the player can transform X into X′=(x1′,x2′,...,xn′), where xi′=-xi, xj′=xj+2dixi for each vj adjacent to vi where vi has exactly di neighbors, and xk′=xk for all other k. 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.
Type
journal article