Game k-Domination Number of Graphs

Rana Khoeilar ； Mustapha Chellali ； Hossein Karami ； Seyed Mahmoud Sheikholeslami

《Tamkang Journal of Mathematics》 52卷4期 (2021/12) Pp. 453-466

https://doi.org/10.5556/j.tkjm.52.2021.3254

摘要

For a positive integer k, a subset D 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 k-domination 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.

關鍵字

domination number ； game domination number ； k-domination number ； game k-domination number