The disjoint domination game

DOI10.1016/J.DISC.2015.04.028MaRDI QIDQ279227zbMATH OpenOpenAlexWikidataFDO

Authors Csilla Bujtás, Zsolt Tuza

Publication date 27 April 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

biased gamecombinatorial gamedisjoint domination gamedominating setgames on graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games involving graphs (91A43)

Abstract: We introduce and study a Maker-Breaker type game in which the issue is to create or avoid two disjoint dominating sets in graphs without isolated vertices. We prove that the maker has a winning strategy on all connected graphs if the game is started by the breaker. This implies the same in the $(2:1)$ biased game also in the maker-start game. It remains open to characterize the maker-win graphs in the maker-start non-biased game, and to analyze the $(a:b)$ biased game for $(a:b)eq(2:1)$. For a more restricted variant of the non-biased game we prove that the maker can win on every graph without isolated vertices.

Recommendations

• THE DOMINATION GAME ON SPLIT GRAPHS
• Connected domination game played on Cartesian products
• Total connected domination game
• Connected domination game
• Fractional domination game
• The domination game played on unions of graphs
• Domination games played on graphs
• Domination game on powers of cycles
• Distance \(d\)-domination games
• The core of discontinuous games

Cites work

• Domination game and an imagination strategy
• Domination game played on trees and spanning subgraphs
• Domination game: effect of edge- and vertex-removal
• Domination game: extremal families of graphs for \(3/5\)-conjectures
• Extremal problems for game domination number
• Hypergraph domination and strong independence
• Realizations of the game domination number
• The domination game played on unions of graphs
• Transversals and domination in uniform hypergraphs

Cited in

(21)

• Domination game and minimal edge cuts
• On graphs with largest possible game domination number
• The variety of domination games
• Connected domination game played on Cartesian products
• Maker-breaker total domination game
• General upper bound on the game domination number
• Maker-breaker domination number
• Fractional domination game
• Trees with equal total domination and game total domination numbers
• Discrepancy games
• Progress towards the total domination game \(\frac{3}{4}\)-conjecture
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• Bounds on the game transversal number in hypergraphs
• The Game of Synchronized Domineering
• Connected domination game
• How long can one bluff in the domination game?
• Paired-domination game played in graphs
• Biased domination games
• Optimal strategies in fractional games: vertex cover and domination
• A proof of the 3/4-conjecture for the total domination game
• Maker-Breaker domination game

This page was built for publication: The disjoint domination game

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