Game $k$-Domination Number of Graphs


  • Rana Khoeilar Azarbaijan Shahid Madani Univeristy
  • Mustapha Chellali University of Blida
  • Hossein Karami Azarbaijan Shahid Madani U niversity
  • Seyed Mahmoud Sheikholeslami Azarbaijan Shahid Madani University



domination number, game k- domination number, k-domination number, game domination number


For a positive integer $k$, a subset $D$ of vertices in a digraph $\overrightarrow{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 $\overrightarrow{G}$. The game $k$-domination number of a simple and undirected graph is defined by the following game. Two players, $\mathcal{A}$ and $\mathcal{D}$, orient the edges of the graph alternately until all edges are oriented. Player $\mathcal{D}$ starts the game, and his goal is to decrease the $k$-domination number of the resulting digraph, while $\mathcal{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 strateries. 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.


R. Aharoni, E. C. Milner and K. Prikry, Unfriendly partitions of a graph, J. Combin. Theory Ser. B 50 (1) (1990) 1–10.

N. Alon, J. Balogh, B. Bollobás and T. Szabó, Game domination number, Discrete Math. 256 (2002), 23–33.

A. Bahremandpour, S.M. Sheikholeslami and L. Volkmann, Roman game domination num- ber of a graph, J. Comb. Optim. 33 (2017), 713–725.

O. Favaron, A. Hansberg and L. Volkmann, On k-domination and minimum degree in graphs, J. Graph Theory 57 (2008) 33–40

O. Favaron, H. Karami, R. Khoeilar, S.M. Sheikholeslami and L. Volkmann, Proof of a conjecture on game domination, J. Graph Theory 64 (2010) 323–329.

T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Dominationin Graphs, Marcel Dekker, Inc., New York, 1998.

L. Lovász and M. D. Plummer, Matching Theory, Annals of Discrete Math. 29, NorthHolland 1986.




How to Cite

Khoeilar, R., Chellali, M., Karami, H., & Sheikholeslami, S. M. (2021). Game $k$-Domination Number of Graphs. Tamkang Journal of Mathematics, 52(4), 453-466.




Most read articles by the same author(s)