Z-domination game

DOI10.1016/J.DISC.2020.112076zbMATH Open1447.05131arXiv1911.08889OpenAlexW3046149740MaRDI QIDQ2198397FDOQ2198397

Sandi Klavžar, Csilla Bujtás, Vesna Iršič

Publication date: 10 September 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: 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 $gamm{a}_{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 $gamm{a}_{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, $gamm{a}_{Zg}(P_n)$ is determined, thus sharpening an earlier related approximate result. It is proved that if $gamm{a}_{Zg}(G)$ is an even number, then $gamm{a}_{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 $gamm{a}_{Zg}(G)=gamma(G)$ are also considered and computational results which compare the studied invariants in the class of trees on at most $16$ vertices reported.

Full work available at URL: https://arxiv.org/abs/1911.08889

Recommendations

• The variety of domination games
• Domination game critical graphs
• Domination game and an imagination strategy
• Domination game: effect of edge- and vertex-removal
• Domination game on paths and cycles

zbMATH Keywords

claw-free graphdomination gamegraph productZ-domination gameweakly claw-free graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57) Graph operations (line graphs, products, etc.) (05C76) Games involving graphs (91A43)

Cites Work

• Zero forcing sets and the minimum rank of graphs
• Domination Game and an Imagination Strategy
• Total version of the domination game
• Extremal Problems for Game Domination Number
• Dominating sequences in graphs
• Game total domination for cycles and paths
• THE DOMINATION GAME ON SPLIT GRAPHS
• Domination game critical graphs
• Characterisation of forests with trivial game domination numbers
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• How long can one bluff in the domination game?
• Zero forcing number, Grundy domination number, and their variants
• Grundy dominating sequences and zero forcing sets
• Domination game on paths and cycles
• The 4/5 upper bound on the game total domination number
• On graphs with largest possible game domination number
• The variety of domination games
• On the game total domination number
• Game total domination critical graphs
• Domination game and minimal edge cuts
• On domination game stable graphs and domination game edge-critical graphs

Cited In (1)

• The Zeckendorf Game

This page was built for publication: Z-domination game

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