Abstract
The 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 γtg(G)≤3/4n, where γ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, φg(H), of a hypergraph H, and prove that if every edge of H has size at least 2, and H ≇C4, then φg(H) ≥ 4/11 (nH + mH), where nH and mH 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 γtg(G) < 8/11 n. As a consequence of this result, the 3/4-Game Total Domination Conjecture is true over the class of graphs with minimum degree at least 2.
Original language | English |
---|---|
Pages (from-to) | 1830-1847 |
Number of pages | 18 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 30 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2016 |
Keywords
- Game transversal
- Hypergraph
- Total domination game
- Transversal
ASJC Scopus subject areas
- General Mathematics