On upper transversals in 3-uniform hypergraphs
type: Item
instance of: scholarly article
title: On upper transversals in 3-uniform hypergraphs
zbMATH Open document ID: 1402.05159
author: Michael A. Henning
author: A. Yeo
published in: The Electronic Journal of Combinatorics
publication date: 2018-11-22T00:00:00Z
full work available at URL: v25i4p27
review text: 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\).
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05D15
zbMATH DE Number: 6983025
zbMATH Keywords: transversal
zbMATH Keywords: upper transversal
zbMATH Keywords: 3-uniform hypergraph
MaRDI profile type: Publication
cites work: Q3993087
cites work: Graph-theoretic parameters concerning domination, independence, and irredundance
cites work: Transversals and domination in uniform hypergraphs
cites work: Total transversals and total domination in uniform hypergraphs
cites work: Two relations between the parameters of independence and irredundance
cites work: Q4842744
cites work: On the independent domination number of graphs with given minimum degree
cites work: Independent domination in graphs: A survey and recent results
cites work: Q4368728
cites work: Q4368729
cites work: A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid theorem
cites work: Hypergraphs with large transversal number
cites work: Minimum size transversals in uniform hypergraphs
cites work: An upper bound for the independent domination number
description: scientific article; zbMATH DE number 6983025