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 graphsgame total domination numberpaths and cyclestotal domination game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) 2-person games (91A05) 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

(24)

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

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)