Effect of predomination and vertex removal on the game total domination number of a graph

DOI10.1016/J.DAM.2018.09.011MaRDI QIDQ1730237zbMATH OpenOpenAlexWikidataFDO

Authors Vesna Iršič

Publication date 11 March 2019

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

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

zbMATH Keywords

critical graphsgame total domination numbertotal 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) Structural characterization of families of graphs (05C75) 2-person games (91A05) Games involving graphs (91A43)

Abstract: The game total domination number, $gamm{a}_g^t$, was introduced by Henning et al. in 2015. In this paper we study the effect of vertex predomination on the game total domination number. We prove that $gamm{a}_g^t(G|v)geqgamm{a}_g^t(G)-2$ holds for all vertices $v$ of a graph $G$ and present infinite families attaining the equality. To achieve this, some new variations of the total domination game are introduced. The effect of vertex removal is also studied. We show that $gamm{a}_g^t(G)leqgamm{a}_g^t(G-v)+4$ and $gamm{a}_g^t\text{'}(G)leq{g}^{\prime }amm{a}_g^t(G-v)+4$.

Recommendations

• Effect of vertex-removal on game total domination numbers
• Domination game: effect of edge- and vertex-removal
• On the game total domination number
• The 4/5 upper bound on the game total domination number
• Game total domination critical graphs

Cites work

• Characterisation of forests with trivial game domination numbers
• Domination game and an imagination strategy
• Domination game critical graphs
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two
• Domination game: effect of edge- and vertex-removal
• Extremal problems for game domination number
• Further progress on the heredity of the game domination number
• Game total domination for cycles and paths
• Progress towards the total domination game \(\frac{3}{4}\)-conjecture
• 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 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

(16)

• Domination game: effect of edge- and vertex-removal
• Predominating a vertex in the connected domination game
• General upper bound on the game domination number
• Game total domination for cyclic bipartite graphs
• Fractional domination game
• Uniform length dominating sequence graphs
• Perfect graphs for domination games
• An introduction to game domination in graphs
• Effect of vertex-removal on game total domination numbers
• On Rall's 1/2-conjecture on the domination game
• Total connected domination game
• Connected domination game: predomination, Staller-start game, and lexicographic products
• Optimal strategies in fractional games: vertex cover and domination
• 4-total domination game critical graphs
• Criticality for maker-breaker domination games with predomination
• Maker-breaker total domination number

This page was built for publication: Effect of predomination and vertex removal on the game total domination number of a graph

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