Domination game: effect of edge- and vertex-removal

DOI10.1016/J.DISC.2014.04.015zbMATH Open1295.05152arXiv1307.5378OpenAlexW2140468832MaRDI QIDQ2017052FDOQ2017052

Authors: Boštjan Brešar, Paul Dorbec, Sandi Klavžar, Gašper Košmrlj 

Publication date: 25 June 2014

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

Abstract: The domination game is played on a graph $G$ by two players, named Dominator and Staller. They alternatively select vertices of $G$ such that each chosen vertex enlarges the set of vertices dominated before the move on it. Dominator's goal is that the game is finished as soon as possible, while Staller wants the game to last as long as possible. It is assumed that both play optimally. Game 1 and Game 2 are variants of the game in which Dominator and Staller has the first move, respectively. The game domination number $gamm{a}_g(G)$, and the Staller-start game domination number $gamm{a_g}^{\prime }(G)$, is the number of vertices chosen in Game 1 and Game 2, respectively. It is proved that if $einE(G)$, then $|gamm{a}_g(G)-gamm{a}_g(G-e)|le2$ and $|gamm{a_g}^{\prime }(G)-gamm{a_g}^{\prime }(G-e)|le2$, and that each of the possibilities here is realizable by connected graphs $G$ for all values of $gamm{a}_g(G)$ and $gamm{a_g}^{\prime }(G)$ larger than 5. For the remaining small values it is either proved that realizations are not possible or realizing examples are provided. It is also proved that if $vinV(G)$, then $gamm{a}_g(G)-gamm{a}_g(G-v)le2$ and $gamm{a_g}^{\prime }(G)-gamm{a_g}^{\prime }(G-v)le2$. Possibilities here are again realizable by connected graphs $G$ in almost all the cases, the exceptional values are treated similarly as in the edge-removal case.

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

Recommendations

• Effect of vertex-removal on game total domination numbers
• Effect of predomination and vertex removal on the game total domination number of a graph
• A game of edge removal on graphs
• A vertex and edge deletion game on graphs
• Effect of an edge subdivision on game domination numbers
• Domination game and minimal edge cuts
• Domination games played on graphs
• The cost of edge removal in graph domination
• Predominating a vertex in the connected domination game
• Vertex-removal in \(K\)-domination

zbMATH Keywords

domination gamegame domination numberedge-removed subgraphvertex-removed subgraph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) 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

• Title not available (Why is that?)
• Domination game and an imagination strategy
• Extremal Problems for Game Domination Number
• Title not available (Why is that?)
• Domination game played on trees and spanning subgraphs
• Realizations of the game domination number
• Domination game: extremal families of graphs for \(3/5\)-conjectures
• Title not available (Why is that?)

Cited In (37)

• Domination game and minimal edge cuts
• Cutting lemma and union lemma for the domination game
• On domination game stable graphs and domination game edge-critical graphs
• Complexity of the game domination problem
• Effect of predomination and vertex removal on the game total domination number of a graph
• Total version of the domination game
• Connected domination game
• Trees with equal total domination and game total domination numbers
• The game total domination problem is log-complete in PSPACE
• An Introduction to Game Domination in Graphs
• The disjoint domination game
• Game total domination for cycles and paths
• On the game total domination number
• Domination game critical graphs
• On the game domination number of graphs with given minimum degree
• On Rall's 1/2-conjecture on the domination game
• Domination game and an imagination strategy
• Optimal strategies in fractional games: vertex cover and domination
• Characterisation of forests with trivial game domination numbers
• Title not available (Why is that?)
• Progress towards the total domination game \(\frac{3}{4}\)-conjecture
• Connected domination game played on Cartesian products
• 4-total domination game critical graphs
• The 4/5 upper bound on the game total domination number
• Fractional domination game
• Domination game on forests
• My Favorite Domination Conjectures in Graph Theory Are Bounded
• Paired-Domination Game Played in Graphs
• Mycielskian of graphs with small game domination number
• General upper bound on the game domination number
• Paired-domination game played on cycles
• Effect of vertex-removal on game total domination numbers
• Effect of an edge subdivision on game domination numbers
• 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
• How long can one bluff in the domination game?
• The 3/5-conjecture for weakly \(S(K_{1, 3})\)-free forests

This page was built for publication: Domination game: effect of edge- and vertex-removal

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