Domination game played on a graph constructed from 1-sum of paths

Abstract

© 2019 by the Mathematical Association of Thailand. All rights reserved. The domination game consists of two players, Dominator and Staller, who construct a dominating set in a given graph G by alternately choosing a vertex from G, with the restriction that in each turn at least one new vertex must be dominated. Dominator wants to minimize the size of the dominating set, while Staller wants to maximize it. In the game, both play optimally. The game domination number γg(G) is the number of vertices chosen in the game which Dominator starts, and γg’(G) is the number of vertices chosen in the game which Staller starts. In this paper these two numbers are analyzed when the game is played on a graph constructed from paths on n vertices, Pn, and on two vertices, P2, by gluing them together at a vertex. This type of operation is called 1-sum. The motivation behind our research is to study the game domination number of a tree that can be constructed from 1-sum of paths.