Paired-domination game played in graphs

Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


In this paper, we continue the study of the domination game in graphs introduced by Brešar, Klavž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 γ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) ≤ 45 n, and this bound is tight. Further we show that if G is (C4, C5)-free, then γgpr(G) ≤ 43 n, where a graph is (C4, C5)-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) ≤ 34 n.

Original languageEnglish
Pages (from-to)79-94
Number of pages16
JournalCommunications in Combinatorics and Optimization
Issue number2
Publication statusPublished - Jun 2019


  • Domination game
  • Paired-domination game
  • Paired-domination number

ASJC Scopus subject areas

  • Control and Optimization
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Paired-domination game played in graphs'. Together they form a unique fingerprint.

Cite this