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.
展开▼
机译：本文研究了与图上支配问题相关的成本分配问题引起的支配集博弈的核心稳定性。令$ G $为邻域矩阵平衡的图。应用线性规划和图论的对偶理论，我们证明了当且仅当每个顶点都属于$ G $的最大2个装箱量时，与$ G $对应的支配博弈才具有稳定的核心。我们还表明，对于与$ G $相对应的占主导地位的固定游戏，如果核心很大，游戏可以扩展或精确，则核心是稳定的。实际上，核心是大的，游戏是可扩展的，游戏是精确的，这被证明是等效的。
展开▼
