Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647803 | Discrete Mathematics | 2013 | 8 Pages |
For k≥2k≥2, let HH be a kk-uniform hypergraph on nn vertices and mm edges. The transversal number τ(H)τ(H) of HH is the minimum number of vertices that intersect every edge. We consider the following question: Is τ(H)≤n/k+m/6τ(H)≤n/k+m/6? For k≥4k≥4, we show that the inequality in the question does not always hold. However, the examples we present all satisfy Δ(H)≥4Δ(H)≥4. A natural question is therefore whether τ(H)≤n/k+m/6τ(H)≤n/k+m/6 holds when Δ(H)≤3Δ(H)≤3. Although we do not know the answer, we prove that the bound holds when Δ(H)≤2Δ(H)≤2, and for that case we characterize the hypergraphs for which equality holds. Furthermore, we prove that the bound holds when k=2k=2 (with no restriction on the maximum degree), and again there we characterize the hypergraphs for which equality holds. Chvátal and McDiarmid [V. Chvátal, C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19–26] proved that the bound holds for k=3k=3 (again with no restriction on the maximum degree). We characterize the extremal hypergraphs in this case.