## Abstract

For k ≥ 2, let H be a k-uniform hypergraph on n vertices and m edges. The transversal number τ (H) of H 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+⌊⌋m)/(⌊3⌋). In particular, for k ∈ {2, 3} we have that (k + 1) τ (H) ≤ n + m. A linear hypergraph is one in which every two distinct edges of H intersect in at most one vertex. In this paper, we consider the following question posed by Henning and Yeo: Is it true that if H is linear, then (k + 1) τ (H) ≤ n + m holds for all k ≥ 2? If k ≥ 4 and we relax the linearity constraint, then this is not always true. We show that if δ (H) ≤ 2, then (k + 1) τ (H) ≤ n + m does hold for all k ≥ 2 and we characterize the hypergraphs achieving equality in this bound.

Original language | English |
---|---|

Pages (from-to) | 231-236 |

Number of pages | 6 |

Journal | European Journal of Combinatorics |

Volume | 36 |

DOIs | |

Publication status | Published - Feb 2014 |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics