Bounds on the game transversal number in hypergraphs

DOI10.1016/J.EJC.2016.07.003zbMATH Open1348.05135arXiv1601.04856OpenAlexW2308662474WikidataQ59072340 ScholiaQ59072340MaRDI QIDQ326647FDOQ326647

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)

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

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

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

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)

Cites Work

• Covering all cliques of a graph
• Small transversals in hypergraphs
• Mr. Paint and Mrs. Correct
• Domination game and an imagination strategy
• Title not available (Why is that?)
• Total version of the domination game
• Extremal problems for game domination number
• A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid theorem
• Hypergraphs with large transversal number and with edge sizes at least four
• Transversals and domination in uniform hypergraphs
• A bound for the game chromatic number of graphs
• The disjoint domination game
• Game matching number of graphs
• Toppling numbers of complete and random graphs
• ON THE COMPLEXITY OF SOME COLORING GAMES
• On-line Ramsey theory
• Hypergraphs with large transversal number
• On-line list colouring of graphs
• Linear hypergraphs with large transversal number and maximum degree two
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• Colouring games
• Efficient graph packing via game colouring
• On-line Ramsey numbers for paths and stars
• Minimum size transversals in uniform hypergraphs
• Total transversals and total domination in uniform hypergraphs
• Radius two trees specify χ‐bounded classes
• On-line Ramsey theory for bounded degree graphs
• Transversals and matchings in 3-uniform hypergraphs
• Game list colouring of graphs

Cited In (17)

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

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)