Journal of the Korean Mathematical Society (대한수학회지)

Korean Mathematical Society (대한수학회)
권호 표지
DOI QR코드

DOI QR Code

BALANCEDNESS OF INTEGER DOMINATION GAMES

  • Kim, Hye-Kyung (Department of Mathematics Catholic University) ;
  • Fang Qizhi (Department of Mathematics Ocean University)
  • Published : 2006.03.01
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we consider cooperative games arising from integer domination problem on graphs. We introduce two games, ${\kappa}-domination$ game and its monotonic relaxed game, and focus on their cores. We first give characterizations of the cores and the relationship between them. Furthermore, a common necessary and sufficient condition for the balancedness of both games is obtained by making use of the technique of linear programming and its duality.

Keywords

References

  1. O. N. Bondareva, Some applications of the methods of linear programming to the theory of cooperative games, (Russian) Problemy Kibernet. 10 (1963), 119-139
  2. I. Curiel, Cooperative game theory and applications. Cooperative games arising from combinatorial optimization problems, Kluwer Academic Publishers, Boston, 1997
  3. X. Deng, T. Ibaraki, and H. Nagamochi, Algorithmic aspects of the core of com- binatorial optimization games, Math. Oper. Res. 24 (1999), no. 3, 751-766 https://doi.org/10.1287/moor.24.3.751
  4. U. Faigle and W. Kern, Partition games and the core of hierarchically convex cost games, (Universiteit Twente, faculteit der toegepaste wiskunde, Memorandum, No. 1269. 1995)
  5. M. R. Garey and D. S. Johnson, Computers and intractability, A guide to the theory of NP-completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, 1979
  6. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of domination in graphs, Marcel Dekker, Inc., New York, 1998
  7. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Domination in graphs. Advanced topics, Marcel Dekker, Inc., New York, 1998
  8. G. Owen, On the core of linear production games, Mathematical Programming 9 (1975), no. 3, 358-370 https://doi.org/10.1007/BF01681356
  9. L. S. Shapley, On balanced sets and cores, Naval Res. Quart. 14 (1967), 453{460 https://doi.org/10.1002/nav.3800140404
  10. L. S. Shapley and M. Shubik, The assignment game, I. The core, Internat. J. Game Theory 1 (1972), no. 2, 111{130
  11. B. van Velzen, Dominating set game, Oper. Res. Lett. 32 (2004), no. 6, 565-573 https://doi.org/10.1016/j.orl.2004.02.004

Cited by

  1. THE CORES OF PAIRED-DOMINATION GAMES vol.31, pp.5, 2015, https://doi.org/10.7858/eamj.2015.052