Domination game: effect of edge- and vertex-removal

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) 2-person games (91A05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: The domination game is played on a graph

G

by two players, named Dominator and Staller. They alternatively select vertices of

G

such that each chosen vertex enlarges the set of vertices dominated before the move on it. Dominator's goal is that the game is finished as soon as possible, while Staller wants the game to last as long as possible. It is assumed that both play optimally. Game 1 and Game 2 are variants of the game in which Dominator and Staller has the first move, respectively. The game domination number

g a m m a_{g} (G)

, and the Staller-start game domination number

g a m m {a_{g}}^{'} (G)

, is the number of vertices chosen in Game 1 and Game 2, respectively. It is proved that if

e i n E (G)

, then

| g a m m a_{g} (G) - g a m m a_{g} (G - e) | l e 2

and

| g a m m {a_{g}}^{'} (G) - g a m m {a_{g}}^{'} (G - e) | l e 2

, and that each of the possibilities here is realizable by connected graphs

G

for all values of

g a m m a_{g} (G)

and

g a m m {a_{g}}^{'} (G)

larger than 5. For the remaining small values it is either proved that realizations are not possible or realizing examples are provided. It is also proved that if

v i n V (G)

, then

g a m m a_{g} (G) - g a m m a_{g} (G - v) l e 2

and

g a m m {a_{g}}^{'} (G) - g a m m {a_{g}}^{'} (G - v) l e 2

. Possibilities here are again realizable by connected graphs

G

in almost all the cases, the exceptional values are treated similarly as in the edge-removal case.

Recommendations

Cites work

Cited in

(42)

This page was built for publication: Domination game: effect of edge- and vertex-removal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2017052)