TY - JOUR
T1 - A note on the Tuza constant ck for small k
AU - Lu, Yun Shan
AU - Wang, Hung Lung
N1 - Publisher Copyright:
© 2023 Elsevier B.V.
PY - 2024/2
Y1 - 2024/2
N2 - 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}.
AB - 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}.
KW - Hypergraph
KW - Transversal number
KW - Tuza constant
UR - http://www.scopus.com/inward/record.url?scp=85174630605&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85174630605&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2023.113756
DO - 10.1016/j.disc.2023.113756
M3 - Article
AN - SCOPUS:85174630605
SN - 0012-365X
VL - 347
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 2
M1 - 113756
ER -