A note on the Tuza constant c_k for small k

DOI10.1016/J.DISC.2023.113756MaRDI QIDQ6184535zbMATH OpenOpenAlexFDO

Authors Yun-Shan Lu, Hung-Lung Wang

Publication date 25 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.14376

zbMATH Keywords

hypergraphtransversal numberTuza constant

Mathematics Subject Classification ID

Hypergraphs (05C65) Transversal (matching) theory (05D15)

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 $au(H)$. The Tuza constant $c_k$ is defined as $supau(H)/(m+n)$, where $H$ ranges over all $k$-uniform hypergrpahs, with $m$ and $n$ being the number of edges and vertices, respectively. We give upper and lower bounds on $c_k$, for $7leqkleq17$.

Recommendations

• Lower bounds on Tuza constants for transversals in linear uniform hypergraphs
• Transversal numbers of uniform hypergraphs
• Transversals in 6-uniform hypergraphs and total domination in graphs with minimum degree six
• Transversals in regular uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 861353 (Why is no real title available?)
• A new upper bound on the total domination number in graphs with minimum degree six
• An upper bound for the transversal numbers of 4-uniform hypergraphs
• Covering all cliques of a graph
• Inequalities on the Lambert \(W\) function and hyperpower function
• Iterative refinement for linear programming
• On the Lambert \(w\) function
• Small transversals in hypergraphs
• Transversal numbers of uniform hypergraphs
• Transversals in 5-uniform hypergraphs and total domination in graphs with minimum degree five
• Transversals in linear uniform hypergraphs

This page was built for publication: A note on the Tuza constant \(c_k\) for small \(k\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6184535)