Back to Search
Start Over
The Disjoint Domination Game
- Publication Year :
- 2014
-
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)\neq (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.<br />18 pages
- Subjects :
- Bondareva–Shapley theorem
Discrete mathematics
Sequential game
Nim
010102 general mathematics
Normal-form game
Combinatorial game theory
ComputingMilieux_PERSONALCOMPUTING
0102 computer and information sciences
01 natural sciences
Theoretical Computer Science
Combinatorics
Strategy
010201 computation theory & mathematics
Repeated game
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
Combinatorics (math.CO)
0101 mathematics
Game tree
05C57, 91A43, 91A46, 05C69
MathematicsofComputing_DISCRETEMATHEMATICS
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....9df9734ac086f63b1c0bb4b242dbca0b