Realizations of the game domination number

Gašper Košmrlj ()
Additional contact information
Gašper Košmrlj: University of Ljubljana

Journal of Combinatorial Optimization, 2014, vol. 28, issue 2, No 8, 447-461

Abstract: Abstract 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 $$\gamma _g$$ . The total number of moves in a Staller-start game is denoted by $$\gamma _g^{\prime }$$ . It is known that $$|\gamma _g(G)-\gamma _g^{\prime }(G)|\le 1$$ for any graph $$G$$ . Graph $$G$$ realizes a pair $$(k,l)$$ if $$\gamma _g(G)=k$$ and $$\gamma _g^{\prime }(G)=l$$ . It is shown that pairs $$(2k,2k-1)$$ for all $$k\ge 2$$ can be realized by a family of 2-connected graphs. We also present 2-connected classes which realize pairs $$(k,k)$$ and $$(k,k+1)$$ . Exact game domination number for combs and 1-connected realization of the pair $$(2k+1,2k)$$ are also given.

Keywords: Domination game; Game domination number; Realizations (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9572-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:28:y:2014:i:2:d:10.1007_s10878-012-9572-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9572-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().