2019/11/20 by Csilla Bujtás, Bujtás, Csilla, Vesna Iršič +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1911.08889
15 pages, 1 figure, 1 table
arxiv created 2019/11/20 · arxiv updated 2019/11/21
The Z-domination game is a variant of the domination game in which each newly selected vertex u in the game must have a not yet dominated neighbor, but after the move all vertices from the closed neighborhood of u are declared to be dominated. The Z-domination game is the fastest among the five natural domination games. The corresponding game Z-domination number of a graph G is denoted by γZg(G). It is proved that the game domination number and the game total domination number of a graph can be expressed as the game Z-domination number of appropriate lexicographic products. Graphs with a Z-insensitive property are introduced and it is proved that if G is Z-insensitive, then γZg(G) is equal to the game domination number of G. Weakly claw-free graphs are defined and proved to be Z-insensitive. As a consequence, γZg(Pn) is determined, thus sharpening an earlier related approximate result. It is proved that if γZg(G) is an even number, then γZg(G) is strictly smaller than the game L-domination number. On the other hand, families of graphs are constructed for which all five game domination numbers coincide. Graphs G with γZg(G) = γ(G) are also considered and computational results which compare the studied invariants in the class of trees on at most 16 vertices reported.