Game k-Domination Number of Graphs.

Khoeilar, Rana; Chellali, Mustapha; Karami, Hossein; Sheikholeslami, Seyed Mahmoud

For a positive integer k, a subsetD of vertices in a digraph →G is a k-dominating set if every vertex not in D has at least k direct predecessors in D. The k-domination number is the minimum cardinality among all k-dominating sets of →G. The game k-domination number of a simple and undirected graph is defined by the following game. Two players, A and D, orient the edges of the graph alternately until all edges are oriented. Player D starts the game, and his goal is to decrease the k-domination number of the resulting digraph, while A is trying to increase it. The game k-domination number of the graph G is the kdomination number of the directed graph resulting from this game. This is well defined if we suppose that both players follow their optimal strategies. We are mainly interested in the study of the game 2-domination number, where some upper bounds will be presented. We also establish a Nordhaus-Gaddum bound for the game 2-domination number of a graph and its complement.

INTEGERS; GRAPH theory; GEOMETRIC vertices; MATHEMATICAL constants; EQUATIONS

Tamkang Journal of Mathematics, 2021, Vol 52, Issue 4, p453

0049-2930

Academic Journal

10.5556/j.tkjm.52.2021.3254