A note on the Tuza constant $c_k$ for small $k$

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 $\tau (H)$. The Tuza constant $c_k$ is defined as $\sup \tau (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 $c_k$. The upper bound improves the known ones for $k\ge 7$, and the lower bound improves the known ones for $k\in \{7,8,10,11,13,14,17\}$.

9 pages, 1 figure, 2 tables

References in corpus (1)

• Linear Programming using Limited-Precision Oracles