A note on the Tuza constant c_k for small k

DOI10.1016/J.DISC.2023.113756arXiv2206.14376OpenAlexW4387888948MaRDI QIDQ6184535FDOQ6184535

Authors: Yun-Shan Lu, Hung-Lung Wang 

Publication date: 25 January 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

zbMATH Keywords

hypergraphtransversal numberTuza constant

Mathematics Subject Classification ID

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

Cites Work

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

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)