Transversals and matchings in 3-uniform hypergraphs

DOI10.1016/J.EJC.2012.07.001zbMATH Open1255.05126arXiv1504.02650OpenAlexW1987632301MaRDI QIDQ691579FDOQ691579

Authors: Michael A. Henning, A. Yeo 

Publication date: 3 December 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $H$ be a $3$-regular $4$-uniform hypergraph on $n$ vertices. The transversal number $au(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 $au(H)le7n/18$. Thomass'{e} and Yeo [Combinatorica 27 (2007), 473--487] improved this bound and showed that $au(H)le8n/21$. We provide a further improvement and prove that $au(H)le3n/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 $Delta(H)le3$, then $au(H)len/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'{e}-Yeo paper [Combinatorica 27 (2007), 473--487].

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

Recommendations

• Hypergraphs with large transversal number
• On upper transversals in 3-uniform hypergraphs
• Bounds on upper transversals in hypergraphs
• Transversal numbers of uniform hypergraphs
• Transversals in uniform hypergraphs with property \((p,2)\)

zbMATH Keywords

connected hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Cited In (19)

• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• A sharp upper bound for the transversal number of \(k\)-uniform connected hypergraphs with given size
• On the transversal number of \(k\)-uniform connected hypergraphs
• Domination in intersecting hypergraphs
• Extremal hypergraphs for matching number and domination number
• The finite projective plane and the 5-uniform linear intersecting hypergraphs with domination number four
• \(d\)-matching in 3-uniform hypergraphs
• A note on improved upper bounds on the transversal number of hypergraphs
• Title not available (Why is that?)
• Domination and total domination in hypergraphs
• Bounds on the game transversal number in hypergraphs
• Total transversals and total domination in uniform hypergraphs
• On the transversal number of rank \(k\) hypergraphs
• A hierarchy of maximal intersecting triple systems
• Matching criticality in intersecting hypergraphs
• Domination and matching in power and generalized power hypergraphs
• Total transversals in hypergraphs and their applications
• Transversals in 4-uniform hypergraphs
• Linear hypergraphs with large transversal number and maximum degree two

This page was built for publication: Transversals and matchings in 3-uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q691579)