Journal of the
Korean Mathematical Society JKMS

In this paper, we study the core stability of the dominating set game which has arisen from the cost allocation problem related to domination problem on graphs. Let $G$ be a graph whose neighborhood matrix is balanced. Applying duality theory of linear programming and graph theory, we prove that the dominating set game corresponding to $G$ has the stable core if and only if every vertex belongs to a maximum 2-packing in $G$. We also show that for dominating set games corresponding to $G$, the core is stable if it is large, the game is extendable, or the game is exact. In fact, the core being large, the game being extendable and the game being exact are shown to be equivalent.

Keywords: dominating set game, balanced, stable core, largeness, exactness, extendability

MSC numbers: 91A12, 68R01