Affine Planes and Transversals in 3-Uniform Linear Hypergraphs

Michael A. Henning*, Anders Yeo

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review


A subset T of vertices in a hypergraph H is a transversal if T has a nonempty intersection with every edge of H. The transversal number τ(H) of H is the minimum size of a transversal in H. A hypergraph H is 3-uniform if every edge of H has size 3. Let H be a 3-uniform hypergraph with nH vertices and mH edges. Tuza (Discrete Math 86:117–126, 1990) and Chvátal and McDiarmid (Combinatorica 12:19–26, 1992) showed that 4τ(H)≤nH+mH. Chvátal and McDiarmid also showed that 6τ(H)≤2nH+mH. The linear hypergraphs achieving equality in these bounds were characterized by the authors (Henning and Yeo in J Graph Theory 59:326–348, 2008; Discrete Math 313:959–966, 2013). In this paper, we show that these bounds can be improved if we impose some structural properties on H. We show that if H does not contain a subhypergraph isomorphic to the affine plane AG(2, 3) of order 3 with two vertices deleted, then 17τ(H)≤5nH+3mH. The total domination number γt(G) of a graph G is the minimum cardinality of a set S of vertices so that every vertex in G is adjacent to some vertex in S. It is known (Archdeacon et al. in J Graph Theory 46:207–210, 2004) that if G is a graph of order n with minimum degree at least 3, then γt(G)≤12n, and that this bound is tight. As a consequence of our hypergraph results, we show that if G is a graph of order n with minimum degree at least 3 that contains no 4-cycles and no specified graph on 12 vertices as a subgraph, then γt(G)≤817n.

TidsskriftGraphs and Combinatorics
Udgave nummer3
Sider (fra-til)867–890
StatusUdgivet - maj 2021

Bibliografisk note

Funding Information:
Research supported in part by the University of Johannesburg.

Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Japan KK part of Springer Nature.


Dyk ned i forskningsemnerne om 'Affine Planes and Transversals in 3-Uniform Linear Hypergraphs'. Sammen danner de et unikt fingeraftryk.