@article {
author = {Henning, M.A. and Haynes, Teresa},
title = {Paired-Domination Game Played in Graphs},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {79-94},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26437.1110},
abstract = {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$.},
keywords = {Paired-domination game,Paired-domination number,Domination game},
url = {http://comb-opt.azaruniv.ac.ir/article_13851.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13851_54f7f80cbf84f62b513594201751c9dc.pdf}
}