Game total domination critical graphs

DOI10.1016/J.DAM.2018.04.014MaRDI QIDQ1801040zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

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
• Effect of predomination and vertex removal on the game total domination number of a graph
• Biased domination games
• Connected domination game
• Game total domination for cycles and paths
• Game total domination for cyclic bipartite graphs
• Predominating a vertex in the connected domination game
• Maker-Breaker total domination game on cubic graphs
• 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)