کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653604 | 1632783 | 2014 | 6 صفحه PDF | دانلود رایگان |
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. Chvátal and McDiarmid [V. Chvátal, C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19–26] proved that τ(H)≤(n+⌊k2⌋m)/(⌊3k2⌋). In particular, for k∈{2,3}k∈{2,3} we have that (k+1)τ(H)≤n+m(k+1)τ(H)≤n+m. A linear hypergraph is one in which every two distinct edges of HH intersect in at most one vertex. In this paper, we consider the following question posed by Henning and Yeo: Is it true that if HH is linear, then (k+1)τ(H)≤n+m(k+1)τ(H)≤n+m holds for all k≥2k≥2? If k≥4k≥4 and we relax the linearity constraint, then this is not always true. We show that if Δ(H)≤2Δ(H)≤2, then (k+1)τ(H)≤n+m(k+1)τ(H)≤n+m does hold for all k≥2k≥2 and we characterize the hypergraphs achieving equality in this bound.
Journal: European Journal of Combinatorics - Volume 36, February 2014, Pages 231–236