Total transversals in hypergraphs and their applications

Let H = (V,E ) be a hypergraph with vertex set V and edge set E of order n_H = | V | and size m_H = |E|. The hypergraph H is k-uniform if every edge of H has size k. Two vertices in H are adjacent if they belong to a common edge in H. A transversal in H is a subset of vertices in H that has a nonempty intersection with every edge of H. A total transversal in H is a transversal T in H with the additional property that every vertex in T is adjacent to some other vertex of T. The total transversal number τ_t (H) of H is the minimum cardinality of a total transversal in H. For k ≥ 2, let b_k = sup_{H ∈Hk} τ_t (H)/(n_H + m_H), where H_k denotes the class of all k -uniform hypergraphs containing no isolated vertices or isolated edges or multiple edges. It is known that b₂ = 2/5, b₃ = 1/3, b₄ ≤ 1/3, and b₅ ≤ 2/7. In this paper, we show that b₄ = 2/7 and b₆ ≤ 1/4. Further, for k ≥ 7, we show that b₇ ≤ 2/9. These results on total transversals have applications in total domination in hypergraphs. A total dominating set in H is a subset of vertices D ⊆ V such that every vertex in H is adjacent to some vertex in D. The total domination number γ_t (H) is the minimum cardinality of a total dominating set in H. The following relationship between the total transversal number and the total domination number of uniform hypergraphs is known: For k ≥ 3 and H ∈ H_k, we have γ_t (H) ≤ (max { 2/k +1, b_k-1}) × n_H. As a consequence of our results on the total transversal number, for k ∈ {2, 3, 4, 5, 6, 7, 8} and a hypergraph H ∈ H_k, we have γ_t (H) ≤ 2n_H/(k + 1).