Abstract
The transversal number τ (H) of a hypergraph H is the minimum
number of vertices that intersect every edge of H. A 6-uniform
hypergraph has all edges of size 6. On 10 November 2000 Tuza
and Vestergaard (2002) conjectured that if H is a 3-regular 6-
uniform hypergraph of order n, then τ (H) ≤ 1
4 n. This conjecture
was recently proven by the Henning and Yeo (2023) and is now
called the Tuza-Vestergaard Theorem. In this paper we extend
the Tuza-Vestergaard Theorem by relaxing the 3-regularity constraint
and allowing bounded maximum degree 4. We present
several applications of the Tuza-Vestergaard Theorem and its
extension. We obtain best known upper bounds to date on the
transversal number of a (general) 6-uniform hypergraph H of
order n and size m. In particular, if H is a 4-regular 6-uniform
hypergraph of order n, then we show that τ (H) ≤ 2
7 n. The
Tuza constant c6 is defined by c6 = sup τ (H)
n(H)+m(H) , where the
supremum is taken over the class of all 6-uniform hypergraphs
H. Since 1990 the exact value of c6 has yet to be determined.
We show that 1
6 ≤ c6 ≤ 16
+ 1
210 , where c6 = 1
6 is conjectured
to be the correct bound. Moreover we show that if G is a graph
of order n with δ(G) ≥ 6, then γt (G) ≤
( 4
13 + 6
217
)
n, where γt (G)
denotes the total domination number of G and γt (G) ≤ 4
13 n is
conjectured to be the correct bound. These bounds improve best
known bounds to date.