Transversals and domination in uniform hypergraphs

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. 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 DV such that for every vertex vVD there exists an edge eE for which ve and eD. 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 k3 the equality sup_H∈Hkγ(H)/(an_H+bm_H)=sup_H∈Hk-1(H)/(an_H+(a+b)m_H) holds, where H_k 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)(n_H+⌊k-3/2⌋m_H)/⌊3(k-1)/2⌋ for all H∈H_k, 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)≤(an_H+bm_H)/(ak+b) for constants b0 and a>-b/k.