## Abstract

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) ≤ ^{4}_{5} n, and this bound is tight. Further we show that if G is (C_{4}, C_{5})-free, then γgpr(G) ≤ _{4}^{3} 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) ≤ ^{3}_{4} n.

Original language | English |
---|---|

Pages (from-to) | 79-94 |

Number of pages | 16 |

Journal | Communications in Combinatorics and Optimization |

Volume | 4 |

Issue number | 2 |

DOIs | |

Publication status | Published - Jun 2019 |

## Keywords

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

## ASJC Scopus subject areas

- Control and Optimization
- Discrete Mathematics and Combinatorics

## Fingerprint

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