# Paired-Domination Game Played in Graphs

Document Type: Original paper

Authors

1 University of Johannesburg

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\$.

Keywords

Main Subjects