TY - JOUR ID - 13851 TI - Paired-Domination Game Played in Graphs JO - Communications in Combinatorics and Optimization JA - CCO LA - en SN - 2538-2128 AU - Henning, M.A. AU - Haynes, Teresa W. AD - University of Johannesburg AD - East Tennessee State University; Department of Mathematics Y1 - 2019 PY - 2019 VL - 4 IS - 2 SP - 79 EP - 94 KW - Paired-domination game KW - Paired-domination number KW - Domination game DO - 10.22049/cco.2019.26437.1110 N2 - In this paper, we continue the study of the domination game in graphs introduced by Bre{\v{s}}ar, Klav{\v{z}}ar, and Rall [SIAM J. Discrete Math. 24 (2010) 979--991]. We study the paired-domination version of the domination game which adds a matching dimension to the game. This game is played on a graph $G$ by two players, named Dominator and Pairer. They alternately take turns choosing vertices of $G$ such that each vertex chosen by Dominator dominates at least one vertex not dominated by the vertices previously chosen, while each vertex chosen by Pairer is a vertex not previously chosen that is a neighbor of the vertex played by Dominator on his previous move. This process eventually produces a paired-dominating set of vertices of $G$; that is, a dominating set in $G$ that induces a subgraph that contains a perfect matching. Dominator wishes to minimize the number of vertices chosen, while Pairer wishes to maximize it. The game paired-domination number $\gamma_{pr}(G)$ of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. Let $G$ be a graph on $n$ vertices with minimum degree at least~$2$. We show that $\gamma_{pr}(G) \le \frac{4}{5}n$, and this bound is tight. Further we show that if $G$ is $(C_4,C_5)$-free, then $\gamma_{pr}(G) \le \frac{3}{4}n$, where a graph is $(C_4,C_5)$-free if it has no induced $4$-cycle or $5$-cycle. If $G$ is $2$-connected and bipartite or if $G$ is $2$-connected and the sum of every two adjacent vertices in $G$ is at least~$5$, then we show that  $\gamma_{pr}(G) \le \frac{3}{4}n$. UR - http://comb-opt.azaruniv.ac.ir/article_13851.html L1 - http://comb-opt.azaruniv.ac.ir/article_13851_54f7f80cbf84f62b513594201751c9dc.pdf ER -