Transversal Game on Hypergraphs and the $\frac{3}{4}$-Conjecture on the Total Domination Game
Csilla Bujtás, Michael A. Henning, Źsolt Tuza · SIAM Journal on Discrete Mathematics · 2016
The $\frac{3}{4}$-Game Total Domination Conjecture posed by Henning, Klavžar, and Rall [Combinatorica, (2016)] states that if $G$ is a graph on $n$ vertices in which every component contains at least three vertices, then $\gamma_{tg}(G) \le \frac{3}{4}n$, where $\gamma_{tg}(G)$ denotes the game total domination number of $G$. Motivated by this conjecture, we raise the problem to a higher level by introducing a transversal game in hypergraphs. We define the game transversal number, $\tau_g(H)$, of a hypergraph $H$, and prove that if every edge of $H$ has size at least 2, and $H cong C_4$, then $\tau_g(H) \le \frac{4}{11}(n_{_H}+m_{_H})$, where $n_{_H}$ and $m_{_H}$ denote the number of vertices and edges, respectively, in $H$. Further, we characterize the hypergraphs achieving equality in this bound. As an application of this result, we prove that if $G$ is a graph on $n$ vertices with minimum degree at least 2, then $\gamma_{{tg}}(G) < \frac{8}{11} n$. As a consequence of this result, the $\frac{3}{4}$-Game Total Domination Conjecture is true over the class of graphs with minimum degree at least 2.