Henning, M., Haynes, T. (2019). Paired-Domination Game Played in Graphs. Communications in Combinatorics and Optimization, 4(2), 79-94. doi: 10.22049/cco.2019.26437.1110

M.A. Henning; Teresa W. Haynes. "Paired-Domination Game Played in Graphs". Communications in Combinatorics and Optimization, 4, 2, 2019, 79-94. doi: 10.22049/cco.2019.26437.1110

Henning, M., Haynes, T. (2019). 'Paired-Domination Game Played in Graphs', Communications in Combinatorics and Optimization, 4(2), pp. 79-94. doi: 10.22049/cco.2019.26437.1110

Henning, M., Haynes, T. Paired-Domination Game Played in Graphs. Communications in Combinatorics and Optimization, 2019; 4(2): 79-94. doi: 10.22049/cco.2019.26437.1110

^{2}East Tennessee State University; Department of Mathematics

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. 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 $gpr(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 $gpr(G) le frac{4}{5}n$, and this bound is tight. Further we show that if $G$ is $(C_4,C_5)$-free, then $gpr(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 $gpr(G) le frac{3}{4}n$.