2021/04/08 by Bujtás, Csilla, Iršič, Vesna, Klavžar, Sandi
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2104.03606
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 γ\rm cg(G) (γ\rm 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 γ\rm cg(G) ≥ 3 and x ∈ V(G), then γ\rm cg(G|x) ≤ 2 γ\rm 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 γ\rm cg(G|x) ≥ \lceil \frac12 γ\rm cg(G) \rceil and the bound is sharp. Graphs G and their vertices x for which γ\rm cg'(G|x) = ∞ holds are also characterized.