Realizations of the game domination number

被引:37
作者
Kosmrlj, Gasper [1 ]
机构
[1] Univ Ljubljana, Fac Math & Phys, Ljubljana, Slovenia
关键词
Domination game; Game domination number; Realizations;
D O I
10.1007/s10878-012-9572-x
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Domination game is a game on a finite graph which includes two players. First player, Dominator, tries to dominate a graph in as few moves as possible; meanwhile the second player, Staller, tries to hold him back and delay the end of the game as long as she can. In each move at least one additional vertex has to be dominated. The number of all moves in the game in which Dominator makes the first move and both players play optimally is called the game domination number and is denoted by . The total number of moves in a Staller-start game is denoted by . It is known that for any graph . Graph realizes a pair if and . It is shown that pairs for all can be realized by a family of 2-connected graphs. We also present 2-connected classes which realize pairs and . Exact game domination number for combs and 1-connected realization of the pair (2k + 1, 2k) are also given.
引用
收藏
页码:447 / 461
页数:15
相关论文
共 6 条
  • [1] Domination game played on trees and spanning subgraphs
    Bresar, Bostjan
    Klavzar, Sandi
    Rall, Douglas F.
    [J]. DISCRETE MATHEMATICS, 2013, 313 (08) : 915 - 923
  • [2] DOMINATION GAME AND AN IMAGINATION STRATEGY
    Bresar, Bostjan
    Klavzar, Sandi
    Rall, Douglas F.
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (03) : 979 - 991
  • [3] Hammack R, 2011, HANDBOOK OF PRODUCT
  • [4] Kinnersley W. B., 2012, GAME DOMINATION GRID
  • [5] Kinnersley WB, 2011, SIAM J DISCRET UNPUB
  • [6] Zamani R., 2011, U ILLINOIS URBANA CH