TRANSVERSALS IN 5-UNIFORM HYPERGRAPHS AND TOTAL DOMINATION IN GRAPHS WITH MINIMUM DEGREE FIVE

摘要

In [9] Thomasse and Yea pose the following problem: Find the minimum c(k) for which every k-uniform hypergraph with n vertices and n edges has a transversal of size at most c(k)n. 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 ckn. It is known that c(2) = 2/3, c(3) = 1/2, and c(4) = 3/7. Thomasse and Yeo show that 4/11 <= c(5) and conjecture that c(5) = 4/11. In this paper we show that c(5) <= 17/44. Thus, 16/44 <= c(5) <= 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.