Paired-domination game played on paths

Aaron D. Gray, Michael A. Henning

Research output: Contribution to journalArticlepeer-review


In this paper, we continue the study of a version of the paired-domination game recently introduced by the authors that embraces both the domination and the matching flavor of the game. The game is played on a graph G by two players, named Dominator and Staller. The players take turns choosing a pair of adjacent vertices of G such that neither vertex in the pair has yet been chosen and the vertices in the pair must dominate at least one vertex not dominated by the previously chosen vertices. 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. 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, and the Staller-start game paired-domination number γgpr′(G) of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper, we determine the game paired-domination numbers γgpr(G) and γgpr′(G) when the graph G is a path Pn on n vertices. We show that γgpr(Pn)=2⌈n3⌉ for all n≥ 2 , unless n= 4 , in which case γgpr(Pn) = 2 , and we show that γgpr′(Pn)=2⌈n+13⌉ for all n≥ 2 , unless n∈ { 3 , 9 } , in which case γgpr′(Pn)=23n . Moreover we describe optimal strategies for both Dominator and Staller for the paired-domination game played on a path.

Original languageEnglish
JournalAequationes Mathematicae
Publication statusAccepted/In press - 2023


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

ASJC Scopus subject areas

  • General Mathematics
  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


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

Cite this