Game Domination Number (2009)

Originator(s): Boštjan Brešar, Sandi Klavžar, Douglas F. Rall    (presented by Jeong Ok Choi - REGS 2009)

Definitions: The domination game on a finite graph G consists of two players D(Dominator) and S(Staller) alternately picking one vertex such that the vertex chosen by a player must enlarge the set of vertices dominated by the chosen vertices. That is, there must be at least one vertex adjacent or equal to the newly chosen vertex that is not adjacent or equal to any previously chosen vertex. In the normal version, D picks first.

The game continues until the set of all vertices chosen by both players becomes a dominating set, and the outcome of the game is the size of that set. The aim of D is to minimize that value, and the aim of S is to maximize it. The game domination number, written γg(G), is the value of the game when D and S play optimally. The value of the game in the variation where S moves first is the Staller-start game domination number, written γ'g(G). ([ABBS] considers a different "domination game" on a graph.)

Background: Since the final set is a dominating set, trivially γg(G)≥γ(G). Brešar, Klavžar, and Rall [BKR] proved that also γg(G)≤2γ(G)-1. To achieve this, D keeps in mind a smallest dominating set T. With each move, D chooses a vertex of T that enlarges the set of dominated vertices, if such a vertex exists. If no such vertices exist, then all vertices dominated by T are already dominated, and hence the set of vertices that has been chosen is already a dominating set. Since D has chosen only vertices of T, the number of vertices chosen is at most 2γ(G)-1.

Conjecture 1: γg(G ◊ H) ≥ ¼γg(G)γg(H), where ◊ denotes cartesian product.

Comments: Conjecture 1 would follow from Vizing's Conjecture [V] that γ(G ◊ H) ≥ γ(G)γ(H) by

γg(G ◊ H) ≥ γ(G ◊ H) ≥ γ(G)γ(H) ≥ ½γg(G) ½γg(H).
Thus Conjecture 1 is a possibly weaker statement than Vizing's Conjecture and might be easier to prove. For Vizing's Conjecture, it is known that 2γ(G ◊ H) ≥ γ(G) γ(H) (see [CS]).

Conjecture 2: A pair (k,l) of positive integers is realizable as (γg(G),γ'g(G)) for some graph G if and only if l∈{k,k+1} or if l=k-1 with k odd.

Comments: Brešar, Klavžar, and Rall [BKR] proved that γg(G)-1 ≤ γ'g(G) ≤ γg(G)+2 . Thus realizability of (k,l) requires k-1 ≤ l ≤ k+2. [BKR] provided constructions to show that the stated condition is sufficient. They conjectured that the remaining cases are not realizable.

Question 3: (West) Which are the extremal graphs for game domination number in terms of domination number? That is, characterize the graphs achieving equality in γg(G) ≥ γ(G) and γg(G) ≤ 2γ(G)-1.

Problem 4: (West) Compute γg(G) on interesting classes of graphs or find sharp bounds for it in terms of other graph parameters.

References:
[ABBS] Alon, Noga; Balogh, József; Bollobás, Béla; Szabó, Tamás; Game domination number. Discrete Math. 256 (2002), no. 1-2, 23--33.
[BKR] Boštjan Brešar, Sandi Klavžar, Douglas F. Rall , Domination game, (probably) submitted, 2009.
[CS] W. E. Clark, S. Suen, An inequality related to Vizing's Conjecture, Electron. J. Combin. 7 (2000), #N4, 3 pp.
[V] Vizing, V. G.: Some unsolved problems in graph theory. Usp. Mat. Nauk 23, (1968) 144, 117--134