Advertisement
Published in:
01-08-2014
Realizations of the game domination number
Published in: Journal of Combinatorial Optimization | Issue 2/2014
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.