Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Affine Planes and Transversals in 3-Uniform Linear Hypergraphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

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 \(\tau (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 \(n_{_H}\) vertices and \(m_{_H}\) edges. Tuza (Discrete Math 86:117–126, 1990) and Chvátal and McDiarmid (Combinatorica 12:19–26, 1992) showed that \(4\tau (H) \le n_{_H}+ m_{_H}\). Chvátal and McDiarmid also showed that \(6\tau (H) \le 2n_{_H}+ m_{_H}\). 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\tau (H) \le 5n_{_H}+ 3m_{_H}\). The total domination number \(\gamma _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 \(\gamma _t(G) \le \frac{1}{2}n\), 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 \(\gamma _t(G) \le \frac{8}{17}n\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Alon, N.: Transversal numbers of uniform hypergraphs. Graphs Combin. 6, 1–4 (1990)

    Article  MathSciNet  Google Scholar 

  2. Archdeacon, D., Ellis-Monaghan, J., Fischer, D., Froncek, D., Lam, P.C.B., Seager, S., Wei, B., Yuster, R.: Some remarks on domination. J. Graph Theory 46, 207–210 (2004)

    Article  MathSciNet  Google Scholar 

  3. Berge, C.: Hypergraphs—Combinatorics of Finite Sets. North-Holland, Amsterdam (1989)

    MATH  Google Scholar 

  4. Bujtás, Cs., Henning, M.A., Tuza, Zs.: Transversals and domination in uniform hypergraphs. Eur. J. Combin. 33, 62–71 (2012)

  5. Bujtás, Cs., Henning, M. A., Tuza, Zs., Yeo, A.: Total transversals and total domination in uniform hypergraphs. Electron. J. Combin. 21(2), #P2.24 (2014)

  6. Chvátal, V., McDiarmid, C.: Small transversals in hypergraphs. Combinatorica 12, 19–26 (1992)

    Article  MathSciNet  Google Scholar 

  7. Dorfling, M., Henning, M.A.: Linear hypergraphs with large transversal number and maximum degree two. Eur. J. Combin. 36, 231–236 (2014)

    Article  MathSciNet  Google Scholar 

  8. Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput. 24(6), 1278–1304 (1995)

    Article  MathSciNet  Google Scholar 

  9. Frendrup, A., Vestergaard, P.D., Yeo, A.: Total domination in partitioned graphs. Graphs Combin. 25(2), 181–196 (2009)

    Article  MathSciNet  Google Scholar 

  10. Henning, M.A., Löwenstein, C.: A characterization of the hypergraphs that achieve equality in the Chvátal–McDiarmid Theorem. Discrete Math. 323, 69–75 (2014)

    Article  MathSciNet  Google Scholar 

  11. Henning, M.A., Yeo, A.: Hypergraphs with large transversal number and with edge sizes at least three. J. Graph Theory 59, 326–348 (2008)

    MathSciNet  MATH  Google Scholar 

  12. Henning, M.A., Yeo, A.: Strong transversals in hypergraphs and double total domination in graphs. SIAM J. Discrete Math. 24(4), 1336–1355 (2010)

    Article  MathSciNet  Google Scholar 

  13. Henning, M.A., Yeo, A.: Total Domination in Graphs (Springer Monographs in Mathematics) (2013). ISBN: 978-1-4614-6524-9 (Print) 978-1-4614-6525-6 (Online)

  14. Henning, M.A., Yeo, A.: Hypergraphs with large transversal number. Discrete Math. 313, 959–966 (2013)

    Article  MathSciNet  Google Scholar 

  15. Henning, M.A., Yeo, A.: On upper transversals in $3$-uniform hypergraphs. Electron. J. Combin. 25(4), #P4.27 (2018)

  16. Henning, M.A., Yeo, A.: Upper transversals in hypergraphs. Eur. J. Combin. 78, 1–12 (2019)

    Article  MathSciNet  Google Scholar 

  17. Henning, M.A., Yeo, A.: Transversals in linear uniform hypergraphs. Springer Developments in Mathematics book series, ISBN 978-3-030-46559-9 (2020)

  18. Khachiyan, L., Boros, E., Elbassioni, K.M., Gurvich, V.: A new algorithm for the hypergraph transversal problem. COCOON, 767–776 (2005)

  19. Khachiyan, L., Boros, E., Elbassioni, K.M., Gurvich, V.: A global parallel algorithm for the hypergraph transversal problem. Inf. Process. Lett. 101(4), 148–155 (2007)

    Article  MathSciNet  Google Scholar 

  20. Lai, F.C., Chang, G.J.: An upper bound for the transversal numbers of 4-uniform hypergraphs. J. Combin. Theory Ser. B. 50, 129–133 (1990)

    Article  MathSciNet  Google Scholar 

  21. Lonc, Z., Warno, K.: Minimum size transversals in uniform hypergraphs. Discrete Math. 313, 2798–2815 (2013)

    Article  MathSciNet  Google Scholar 

  22. Thomassé, S., Yeo, A.: Total domination of graphs and small transversals of hypergraphs. Combinatorica 27, 473–487 (2007)

    Article  MathSciNet  Google Scholar 

  23. Tuza, Zs.: Covering all cliques of a graph. Discrete Math. 86, 117–126 (1990)

  24. Wild, M., Janson, S., Wagner, S., Laurie, D.: Coupon collecting and transversals of hypergraphs. Discrete Math. Theor. Comput. Sci. 15(2), 259–270 (2013)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa

    Michael A. Henning & Anders Yeo

  2. Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, 5230, Odense M, Denmark

    Anders Yeo

Authors
  1. Michael A. Henning
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anders Yeo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael A. Henning.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Research supported in part by the University of Johannesburg.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Henning, M.A., Yeo, A. Affine Planes and Transversals in 3-Uniform Linear Hypergraphs. Graphs and Combinatorics 37, 867–890 (2021). https://doi.org/10.1007/s00373-021-02285-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-021-02285-x

Keywords

Mathematics Subject Classification

Search

Navigation