Domination game on uniform hypergraphs

DOI10.1016/J.DAM.2018.11.013zbMATH Open1407.05159arXiv1710.00298OpenAlexW2963150039WikidataQ128719450 ScholiaQ128719450MaRDI QIDQ1732097FDOQ1732097

Authors: Csilla Bujtás, Balázs Patkós, Zsolt Tuza, Máté Vizer 

Publication date: 22 March 2019

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

Abstract: In this paper we introduce and study the domination game on hypergraphs. This is played on a hypergraph $mathcalH$ by two players, namely Dominator and Staller, who alternately select vertices such that each selected vertex enlarges the set of vertices dominated so far. The game is over if all vertices of $mathcalH$ are dominated. Dominator aims to finish the game as soon as possible, while Staller aims to delay the end of the game. If each player plays optimally and Dominator starts, the length of the game is the invariant `game domination number' denoted by $gamm{a}_g(mathcalH)$. This definition is the generalization of the domination game played on graphs and it is a special case of the transversal game on hypergraphs. After some basic general results, we establish an asymptotically tight upper bound on the game domination number of $k$-uniform hypergraphs. In the remaining part of the paper we prove that $gamm{a}_g(mathcalH)le5n/9$ if $mathcalH$ is a 3-uniform hypergraph of order $n$ and does not contain isolated vertices. This also implies the following new result for graphs: If $G$ is an isolate-free graph on $n$ vertices and each of its edges is contained in a triangle, then $gamm{a}_g(G)le5n/9$.

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

Recommendations

• The domination game played on unions of graphs
• Domination games played on graphs
• Domination games on infinite graphs
• An introduction to game domination in graphs
• THE DOMINATION GAME ON SPLIT GRAPHS
• Domination in hypergraphs
• Game $k$-Domination Number of Graphs
• On graphs with largest possible game domination number
• Domination game played on trees and spanning subgraphs
• Domination game critical graphs

zbMATH Keywords

uniform hypergraphsdomination gamegame domination number

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) Hypergraphs (05C65) Games involving graphs (91A43)

Cites Work

• Title not available (Why is that?)
• Transversal numbers of uniform hypergraphs
• Domination game and an imagination strategy
• The domination game played on unions of graphs
• Total domination in graphs
• Total version of the domination game
• Extremal problems for game domination number
• Domination in hypergraphs
• A characterization of hypergraphs with large domination number
• Hypergraphs with large transversal number and with edge sizes at least four
• Hypergraphs with large domination number and with edge sizes at least three
• Transversals and domination in uniform hypergraphs
• Domination game played on trees and spanning subgraphs
• Realizations of the game domination number
• Domination game on forests
• Game total domination for cycles and paths
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two
• On the game domination number of graphs with given minimum degree
• Game matching number of graphs
• Equality of domination and transversal numbers in hypergraphs
• The 3/5-conjecture for weakly \(S(K_{1, 3})\)-free forests
• On-line Ramsey theory
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• Colouring games
• Bounds on the game transversal number in hypergraphs
• Efficient graph packing via game colouring
• Total transversals and total domination in uniform hypergraphs
• Game list colouring of graphs
• Game saturation of intersecting families
• The minimum number of vertices in uniform hypergraphs with given domination number
• How long can one bluff in the domination game?
• Domination game: extremal families for the 3/5-conjecture for forests
• The 4/5 upper bound on the game total domination number
• On graphs with largest possible game domination number
• Matching and domination numbers in \(r\)-uniform hypergraphs
• On the game total domination number
• Game total domination critical graphs
• Trees with equal total domination and game total domination numbers
• On domination game stable graphs and domination game edge-critical graphs

Cited In (11)

• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• THE DOMINATION GAME ON SPLIT GRAPHS
• The domination game played on unions of graphs
• Some combinatorial algorithms on the dominating number of anti-rank \(k\) hypergraphs
• Optimal strategies in fractional games: vertex cover and domination
• Domination game on paths and cycles
• Domination game played on trees and spanning subgraphs
• Fractional domination game
• Domination games on infinite graphs
• General upper bound on the game domination number
• A proof of the 3/4-conjecture for the total domination game

This page was built for publication: Domination game on uniform hypergraphs

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