Game total domination critical graphs

DOI10.1016/J.DAM.2018.04.014zbMATH Open1398.05135arXiv1709.06069OpenAlexW2963989423WikidataQ129882638 ScholiaQ129882638MaRDI QIDQ1801040FDOQ1801040

Authors: Michael A. Henning, Sandi Klavžar, Douglas F. Rall 

Publication date: 26 October 2018

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

Abstract: In the total domination game played on a graph $G$, players Dominator and Staller alternately select vertices of $G$, as long as possible, such that each vertex chosen increases the number of vertices totally dominated. Dominator (Staller) wishes to minimize (maximize) the number of vertices selected. The game total domination number, $gamm{a}_{mtg}(G)$, of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. If a vertex $v$ of $G$ is declared to be already totally dominated, then we denote this graph by $G|v$. In this paper the total domination game critical graphs are introduced as the graphs $G$ for which $gamm{a}_{mtg}(G|v)<gamm{a}_{mtg}(G)$ holds for every vertex $v$ in $G$. If $gamm{a}_{mtg}(G)=k$, then $G$ is called $k$-$gamm{a}_{mtg}$-critical. It is proved that the cycle $C_n$ is $gamm{a}_{mtg}$-critical if and only if $npmod6in0,1,3$ and that the path $P_n$ is $gamm{a}_{mtg}$-critical if and only if $npmod6in2,4$. $2$-$gamm{a}_{mtg}$-critical and $3$-$gamm{a}_{mtg}$-critical graphs are also characterized as well as $3$-$gamm{a}_{mtg}$-critical joins of graphs.

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

Recommendations

• Game total domination for cycles and paths
• Infinite families of circular and Möbius ladders that are total domination game critical
• Domination game critical graphs
• Game total domination for cyclic bipartite graphs
• On the game total domination number

zbMATH Keywords

critical graphspaths and cyclestotal domination gamegame total domination number

Mathematics Subject Classification ID

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)

Cites Work

• Domination game and an imagination strategy
• Complexity of the game domination problem
• The domination game played on unions of graphs
• Total domination in graphs
• Total version of the domination game
• Extremal problems for game domination number
• Realizations of the game domination number
• Domination game: extremal families of graphs for \(3/5\)-conjectures
• Domination game on forests
• Game total domination for cycles and paths
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two
• On the game domination number of graphs with given minimum degree
• Domination game critical graphs
• The 3/5-conjecture for weakly \(S(K_{1, 3})\)-free forests
• 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?
• Domination game: extremal families for the 3/5-conjecture for forests
• The 4/5 upper bound on the game total domination number
• Progress towards the total domination game \(\frac{3}{4}\)-conjecture
• Trees with equal total domination and game total domination numbers
• The game total domination problem is log-complete in PSPACE

Cited In (21)

• On game chromatic vertex-critical graphs
• On domination game stable graphs and domination game edge-critical graphs
• Connected domination game: predomination, Staller-start game, and lexicographic products
• Biased domination games
• Effect of predomination and vertex removal on the game total domination number of a graph
• Connected domination game
• Game total domination for cycles and paths
• Game total domination for cyclic bipartite graphs
• Maker-Breaker total domination game on cubic graphs
• Predominating a vertex in the connected domination game
• Domination game critical graphs
• Maker-breaker total domination game
• 4-total domination game critical graphs
• Fractional domination game
• Domination game on uniform hypergraphs
• General upper bound on the game domination number
• An introduction to game domination in graphs
• Z-domination game
• Infinite families of circular and Möbius ladders that are total domination game critical
• The variety of domination games
• Perfect graphs for domination games

This page was built for publication: Game total domination critical graphs

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