Transversals and domination in uniform hypergraphs

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

► Let HH be a hypergraph with nHnH vertices and mHmH edges.
► Let HkHk be the class of kk-uniform hypergraphs containing no isolated vertices.
► Let τ(H)τ(H) and γ(H)γ(H) denote the transversal number and domination number of HH, respectively.
► For k≥3k≥3 an integer and for reals a,b≥0a,b≥0, the equality supH∈Hkγ(H)/(anH+bmH)=supH∈Hk−1τ(H)/(anH+(a+b)mH)supH∈Hkγ(H)/(anH+bmH)=supH∈Hk−1τ(H)/(anH+(a+b)mH) holds.