Transversals in 5-uniform hypergraphs and total domination in graphs with minimum degree five

Abstract

In [9] Thomassé and Yeo pose the following problem: Find the mini-
mum c_k for which every k-uniform hypergraph with n vertices and n edges has a transversal of size at most c_kn. A direct consequence of this result is that every graph of order n with minimum degree at least k has a total dominating set of cardinality at most c_kn. It is known that c₂ = 2/3, c₃ = 1/2, and c₄ = 3/7. Thomassé and Yeo show that 4/11 ≤ c₅ and conjecture that c₅ = 4/11. In this paper we show that c₅ ≤ 17/44. Thus, 16/44 ≤ c₅ ≤ 17/44. More generally we prove that every 5-uniform hypergraph on n vertices and m edges has a transversal with no more than (10n+7m)/44 vertices. Consequently, every graph on n vertices with minimum degree at least five has total domination number at most 17n/44.

Keywords: Transversal, hypergraph, total domination in graphs.