MathDB

The 3/5-conjecture for the game domination number

Consider a simple undirected graph GG with vertex set V(G)V(G) and order n=∣V(G)∣n=|V(G)|. The game domination number γg(G)\gamma_g(G) is the value of the domination game on GG when Dominator starts and both players play optimally; a graph is isolate-free when it has no isolated vertices. The 3/5-conjecture. If GG is an isolate-free graph of order nn, then

γg(G)≤3n/5.\gamma_g(G) \le 3n/5.

This conjecture is a central problem in the study of the domination game and proposes a sharp universal upper bound for isolate-free graphs. The supplied text gives no resolution status.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. The 3/5-conjecture for the game domination number

    Let GG be an isolate-free graph of order nn, and let b[1mγg(G)b[0mb[1m\gamma_g(G)b[0m denote its game domination number, namely the number of turns in the domination game when Dominator starts and both players play optimally.

    3/5-conjecture.

    γg(G)≤3n5.\gamma_g(G) \leq \frac{3n}{5}.

    This conjecture gives an upper bound on the duration of the domination game in terms of the order of the graph. The supplied text does not indicate whether it has been resolved.

    source: Csilla Bujtás, “On the game domination number of graphs with given minimum degree”, arXiv:1406.7372 (2014).

Sources & referencesView supporting material

Primary source

Csilla Bujtás, “General upper bound on the game domination number”, arXiv:2002.00105 (2020).

domination-gamesgraph-theory

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.