Game $k$-Domination Number of Graphs

Authors

  • Rana Khoeilar Azarbaijan Shahid Madani Univeristy
  • Mustapha Chellali University of Blida https://orcid.org/0000-0001-5231-6195
  • Hossein Karami Azarbaijan Shahid Madani U niversity
  • Seyed Mahmoud Sheikholeslami Azarbaijan Shahid Madani University

DOI:

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

Keywords:

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

Abstract

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.

References

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.

Downloads

Published

2021-10-30

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. https://doi.org/10.5556/j.tkjm.52.2021.3254

Issue

Section

Papers

Most read articles by the same author(s)