We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Predominating a Vertex in the Connected Domination Game.
- Authors
Bujtás, Csilla; Iršič, Vesna; Klavžar, Sandi
- Abstract
The connected domination game is played just as the domination game, with an additional requirement that at each stage of the game the vertices played induce a connected subgraph. The number of moves in a D-game (an S-game, resp.) on a graph G when both players play optimally is denoted by γ cg (G) ( γ cg ′ (G) , resp.). Connected Game Continuation Principle is established as a substitute for the classical Continuation Principle which does not hold for the connected domination game. Let G|x denote the graph G together with a declaration that the vertex x is already dominated. The first main result asserts that if G is a graph with γ cg (G) ≥ 3 and x ∈ V (G) , then γ cg (G | x) ≤ 2 γ cg (G) - 3 and the bound is sharp. The second main theorem states that if G is a graph with n (G) ≥ 2 and x ∈ V (G) , then γ cg (G | x) ≥ 1 2 γ cg (G) and the bound is sharp. Graphs G and their vertices x for which γ cg ′ (G | x) = ∞ holds are also characterized.
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 3, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02478-y