On upper transversals in 3-uniform hypergraphs
Summary: A set \(S\) of vertices in a hypergraph \(H\) is a transversal if it has a nonempty intersection with every edge of \(H\). The upper transversal number \(\Upsilon(H)\) of \(H\) is the maximum cardinality of a minimal transversal in \(H\). We show that if \(H\) is a connected \(3\)-uniform hypergraph of order \(n\), then \(\Upsilon(H) > 1.4855 \root{3}\of{n} - 2\). For \(n\) sufficiently large, we construct infinitely many connected \(3\)-uniform hypergraphs, \(H\), of order \(n\) satisfying \(\Upsilon(H) < 2.5199 \root{3}\of{n}\). We conjecture that \(\sup_{n\rightarrow\infty} \bigg(\text{inf}\frac{\Upsilon(H)}{\root{3}\of{n}}\bigg) = \root{3}\of{16}\), where the infimum is taken over all connected \(3\)-uniform hypergraphs \(H\) of order \(n\).
- A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid theorem
- An upper bound for the independent domination number
- Graph-theoretic parameters concerning domination, independence, and irredundance
- scientific article; zbMATH DE number 43754 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1095172 (Why is no real title available?)
- scientific article; zbMATH DE number 786167 (Why is no real title available?)
- Hypergraphs with large transversal number
- Independent domination in graphs: A survey and recent results
- Minimum size transversals in uniform hypergraphs
- On the independent domination number of graphs with given minimum degree
- Total transversals and total domination in uniform hypergraphs
- Transversals and domination in uniform hypergraphs
- Two relations between the parameters of independence and irredundance
- A note on fractional disjoint transversals in hypergraphs
- Affine planes and transversals in 3-uniform linear hypergraphs
- (In)approximability of maximum minimal FVS
- A sharp upper bound for the transversal number of k-uniform connected hypergraphs with given size
- Bounds on upper transversals in hypergraphs
- Upper transversals in hypergraphs
- scientific article; zbMATH DE number 165088 (Why is no real title available?)
- On the transversal number of k-uniform connected hypergraphs
- The Tuza–Vestergaard Theorem
- An upper bound for the transversal number of connected k-uniform hypergraphs
- On the number of \(A\)-transversals in hypergraphs
- Transversals and matchings in 3-uniform hypergraphs
- On the number of minimal transversals in 3-uniform hypergraphs
This page was built for publication: On upper transversals in 3-uniform hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1627202)
