Abstract
For a hypergraph H, the transversal is a subset of vertices whose intersection with every edge is nonempty. The cardinality of a minimum transversal is the transversal number of H, denoted by τ(H). The Tuza constant ck is defined as supτ(H)/(m+n), where H ranges over all k-uniform hypergraphs, with m and n being the number of edges and vertices, respectively. We give an upper bound and a lower bound on ck. The upper bound improves the known ones for k≥7, and the lower bound improves the known ones for k∈{7,8,10,11,13,14,17}.
Original language | English |
---|---|
Article number | 113756 |
Journal | Discrete Mathematics |
Volume | 347 |
Issue number | 2 |
DOIs | |
Publication status | Published - 2024 Feb |
Keywords
- Hypergraph
- Transversal number
- Tuza constant
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics