Bounds on the game transversal number in hypergraphs

DOI10.1016/J.EJC.2016.07.003MaRDI QIDQ326647zbMATH OpenOpenAlexWikidataFDO

Authors Csilla Bujtás, Michael A. Henning, Zsolt Tuza

Publication date 12 October 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

transversal continuation principletransversal game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Transversal (matching) theory (05D15) Games involving graphs (91A43)

Abstract: Let $H=(V,E)$ be a hypergraph with vertex set $V$ and edge set $E$ of order $H=|V|$ and size $mH=|E|$. A transversal in $H$ is a subset of vertices in $H$ that has a nonempty intersection with every edge of $H$. A vertex hits an edge if it belongs to that edge. The transversal game played on $H$ involves of two players, emph{Edge-hitter} and emph{Staller}, who take turns choosing a vertex from $H$. Each vertex chosen must hit at least one edge not hit by the vertices previously chosen. The game ends when the set of vertices chosen becomes a transversal in $H$. Edge-hitter wishes to minimize the number of vertices chosen in the game, while Staller wishes to maximize it. The emph{game transversal number}, $a{u}_g(H)$, of $H$ is the number of vertices chosen when Edge-hitter starts the game and both players play optimally. We compare the game transversal number of a hypergraph with its transversal number, and also present an important fact concerning the monotonicity of $a{u}_g$, that we call the Transversal Continuation Principle. It is known that if $H$ is a hypergraph with all edges of size at least~$2$, and $H$ is not a $4$-cycle, then $a{u}_g(H)lefrac411(H+mH)$; and if $H$ is a (loopless) graph, then $a{u}_g(H)lefrac13(H+mH+1)$. We prove that if $H$ is a $3$-uniform hypergraph, then $a{u}_g(H)lefrac516(H+mH)$, and if $H$ is $4$-uniform, then $a{u}_g(H)lefrac71252(H+mH)$.

Recommendations

• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• Bounds on upper transversals in hypergraphs
• scientific article; zbMATH DE number 7666858
• A note on improved upper bounds on the transversal number of hypergraphs
• Total transversals in hypergraphs and their applications
• scientific article; zbMATH DE number 4200245
• Transversal numbers of uniform hypergraphs
• A bound for the game chromatic number of graphs
• Bounded transversals in multipartite graphs
• On the transversal number of rank \(k\) hypergraphs

Cites work

• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• A bound for the game chromatic number of graphs
• A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid theorem
• Colouring games
• Covering all cliques of a graph
• Domination game and an imagination strategy
• Efficient graph packing via game colouring
• Extremal problems for game domination number
• Game list colouring of graphs
• Game matching number of graphs
• Hypergraphs with large transversal number
• Hypergraphs with large transversal number and with edge sizes at least four
• Linear hypergraphs with large transversal number and maximum degree two
• Minimum size transversals in uniform hypergraphs
• Mr. Paint and Mrs. Correct
• ON THE COMPLEXITY OF SOME COLORING GAMES
• On-line Ramsey numbers for paths and stars
• On-line Ramsey theory
• On-line Ramsey theory for bounded degree graphs
• On-line list colouring of graphs
• Radius two trees specify χ‐bounded classes
• Small transversals in hypergraphs
• The disjoint domination game
• Toppling numbers of complete and random 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
• Transversals and domination in uniform hypergraphs
• Transversals and matchings in 3-uniform hypergraphs

Cited in

(17)

• On the game total domination number
• The matcher game played in graphs
• Optimal strategies in fractional games: vertex cover and domination
• Domination game on uniform hypergraphs
• Transversals in hypergraphs through a new combinatorial game
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• The \((a, b)\)-monochromatic transversal game on clique-hypergraphs of powers of cycles
• Domination game and minimal edge cuts
• Bounds on upper transversals in hypergraphs
• Fractional domination game
• Paired-domination game played in graphs
• General upper bound on the game domination number
• Connected domination game played on Cartesian products
• A combinatorial game over biclique-hypergraphs of powers of paths and of powers of cycles through monochromatic transversals
• Trees with equal total domination and game total domination numbers
• An introduction to game domination in graphs
• A proof of the 3/4-conjecture for the total domination game

This page was built for publication: Bounds on the game transversal number in hypergraphs

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