Transversals and domination in uniform hypergraphs

AbstractLet H=(V,E) be a hypergraph with vertex set V and edge set E of order nH=|V| and size mH=|E|. A transversal in H is a subset of vertices in H that has a nonempty intersection with every edge of H. The transversal number τ(H) of H is the minimum size of a transversal in H. A dominating set in H is a subset of vertices D⊆V such that for every vertex v∈V∖D there exists an edge e∈E for which v∈e and e∩D≠0̸. The domination number γ(H) is the minimum cardinality of a dominating set in H. A hypergraph H is k-uniform if every edge of H has size k. We establish the following relationship between the transversal number and the domination number of uniform hypergraphs. For any two nonnegative reals a and b and for every integer k≥3 the equality supH∈Hkγ(H)/(anH+bmH)=supH∈Hk−1τ(H)/(anH+(a+b)mH) holds, where Hk denotes the class of all k-uniform hypergraphs containing no isolated vertices. As a consequence of this result, we establish upper bounds on the domination number of a k-uniform hypergraph with minimum degree at least 1. In particular, we show that if k≥3, then γ(H)≤(nH+⌊k−32⌋mH)/⌊3(k−1)2⌋ for all H∈Hk, and this bound is sharp. More generally, for k=2 and k=3 we prove that all the essential upper bounds can be written in the unified form γ(H)≤(anH+bmH)/(ak+b) for constants b≥0 and a>−b/k