A note on balancedness of dominating set games

In this paper we consider the balancedness of dominating set games, introduced by Velzen. We establish a new kind of 0–1 program formulation to model the domination problem on graphs, and give a strong connection between LP relaxation of this 0–1 program and the cost allocation problem concerning the core of a dominating set game. Duality theory on Lagrange dual is the main technique in our proof. In particular, we use this insight to give the equivalence of the balancedness for two different dominating set games.