Game domination numbers of a disjoint union of chains and cycles of complete graphs

CJM Vol. 11 (December 2019), pp. 10 – 25.


Abstract: 

The domination game played on a graph $G$ consists of two players, Dominator and Staller, who alternate taking turns choosing a vertex from G such that whenever a vertex is chosen, at least one additional vertex is dominated. Playing a vertex will make all vertices in its closed neighborhood dominated. The game ends when all vertices are dominated i.e. the chosen vertices form a dominating set. Dominator's goal is to finish the game as soon as possible, and Staller's goal is to prolong it as much as possible. The game domination number is the total number of chosen vertices after the game ends when Dominator and Staller play the game by using optimal strategies. In this paper, we determine the game domination numbers of a disjoint union of chains and cycles of complete graphs together with optimal strategies for Dominator and Staller.


2000 Mathematics Subject Classification: 

Full Paper (PDF): 
AttachmentSize
PDF icon CJM2019-02.pdf206.37 KB