Total connected domination game

DOI10.7494/OPMATH.2021.41.4.453MaRDI QIDQ5161631zbMATH OpenOpenAlexFDO

Authors Csilla Bujtás, Michael A. Henning, Vesna Iršič, Sandi Klavžar

Publication date 1 November 2021

Published in Opuscula Mathematica (Search for Journal in Brave)

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

zbMATH Keywords

treegraph productconnected domination gametotal connected domination game

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) Graph operations (line graphs, products, etc.) (05C76) Games involving graphs (91A43)

Abstract: The (total) connected domination game on a graph $G$ is played by two players, Dominator and Staller, according to the standard (total) domination game with the additional requirement that at each stage of the game the selected vertices induce a connected subgraph of $G$. If Dominator starts the game and both players play optimally, then the number of vertices selected during the game is the (total) connected game domination number ($gamm{a}_{mtcg}(G)$) $gamm{a}_{mcg}(G)$ of $G$. We show that $gamm{a}_{mtcg}(G)ingamm{a}_{mcg}(G),gamm{a}_{mcg}(G)+1,gamm{a}_{mcg}(G)+2$, and consequently define $G$ as Class $i$ if $gamm{a}_{mtcg}(G)=gamm{a}_{mcg}+i$ for $iin0,1,2$. A large family of Class $0$ graphs is constructed which contains all connected Cartesian product graphs and connected direct product graphs with minumum degree at least $2$. We show that no tree is Class $2$ and characterize Class $1$ trees. We provide an infinite family of Class $2$ bipartite graphs.

Recommendations

• Connected domination game
• Predominating a vertex in the connected domination game
• Realizations of the game domination number
• On the game total domination number
• The 4/5 upper bound on the game total domination number

Cites work

• Connected domination game
• Connected domination game played on Cartesian products
• Domination game and an imagination strategy
• Domination game and minimal edge cuts
• Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs
• Effect of predomination and vertex removal on the game total domination number of a graph
• Extremal problems for game domination number
• Game total domination for cycles and paths
• Handbook of product graphs
• On domination game stable graphs and domination game edge-critical graphs
• On the game domination number of graphs with given minimum degree
• On the game total domination number
• Progress towards the total domination game \(\frac{3}{4}\)-conjecture
• THE DOMINATION GAME ON SPLIT GRAPHS
• 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

Cited in

(9)

• Connected domination game: predomination, Staller-start game, and lexicographic products
• Connected domination game
• The disjoint domination game
• Predominating a vertex in the connected domination game
• Connector-breaker games on random boards
• The link smoothing game
• 4-total domination game critical graphs
• Games of Connectivity
• Paired-domination in binary trees

This page was built for publication: Total connected domination game

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