Domination game on uniform hypergraphs

DOI10.1016/J.DAM.2018.11.013MaRDI QIDQ1732097zbMATH OpenOpenAlexWikidataFDO

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)

Full work available at URL https://arxiv.org/abs/1710.00298, http://real.mtak.hu/92797/1/1710.00298v1.pdf

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)

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$.

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

Cites work

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

Cited in

(11)

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