Transversal game on hypergraphs and the 3/4-conjecture on the total domination game

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

Research output: Contribution to journalArticlepeer-review

36 Citations (Scopus)

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 languageEnglish
Pages (from-to)1830-1847
Number of pages18
JournalSIAM Journal on Discrete Mathematics
Volume30
Issue number3
DOIs
Publication statusPublished - 2016

Keywords

  • Game transversal
  • Hypergraph
  • Total domination game
  • Transversal

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Transversal game on hypergraphs and the 3/4-conjecture on the total domination game'. Together they form a unique fingerprint.

Cite this