2015/04/10 by Michael A. Henning, Henning, Michael A., Anders Yeo +1
Computer Science · Engineering · Mathematics · #05C65 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05C65
paper · pdf · doi:10.48550/arxiv.1504.02650
41 pages
arxiv created 2015/04/10 · openalex publication_date 2015/04/10 · arxiv updated 2015/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let H be a 3-regular 4-uniform hypergraph on n vertices. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [J. Combin. Theory Ser. B 50 (1990), 129--133] proved that τ(H) ≤ 7n/18. Thomassé and Yeo [Combinatorica 27 (2007), 473--487] improved this bound and showed that τ(H) ≤ 8n/21. We provide a further improvement and prove that τ(H) ≤ 3n/8, which is best possible due to a hypergraph of order eight. More generally, we show that if H is a 4-uniform hypergraph on n vertices and m edges with maximum degree Δ(H) ≤ 3, then τ(H) ≤ n/4 + m/6, which proves a known conjecture. We show that an easy corollary of our main result is that the total domination number of a graph on n vertices with minimum degree at least~4 is at most 3n/7, which was the main result of the Thomassé-Yeo paper [Combinatorica 27 (2007), 473--487].