Return to search

Paired-Domination Game Played in Graphs<sup>∗</sup>

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.

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-11227
Date01 June 2019
CreatorsHaynes, Teresa W., Henning, Michael A.
PublisherDigital Commons @ East Tennessee State University
Source SetsEast Tennessee State University
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceETSU Faculty Works
Rightshttp://creativecommons.org/licenses/by-sa/4.0/

Page generated in 0.0021 seconds