A note on the Tuza constant ck for small k

Yun Shan Lu, Hung Lung Wang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number113756
JournalDiscrete Mathematics
Volume347
Issue number2
DOIs
Publication statusPublished - 2024 Feb

Keywords

  • Hypergraph
  • Transversal number
  • Tuza constant

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A note on the Tuza constant ck for small k'. Together they form a unique fingerprint.

Cite this