We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Paired-domination game played on paths.
- Authors
Gray, Aaron D.; Henning, Michael A.
- Abstract
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 P n on n vertices. We show that γ gpr (P n) = 2 ⌈ n 3 ⌉ for all n ≥ 2 , unless n = 4 , in which case γ gpr (P n) = 2 , and we show that γ gpr ′ (P n) = 2 ⌈ n + 1 3 ⌉ for all n ≥ 2 , unless n ∈ { 3 , 9 } , in which case γ gpr ′ (P n) = 2 3 n . Moreover we describe optimal strategies for both Dominator and Staller for the paired-domination game played on a path.
- Subjects
DOMINATING set; RECREATIONAL mathematics; FLAVOR; GAMES
- Publication
Aequationes Mathematicae, 2024, Vol 98, Issue 5, p1391
- ISSN
0001-9054
- Publication type
Article
- DOI
10.1007/s00010-023-00995-6