# Hypergraphs with large transversal number and with edge sizes at least four

Michael Henning; Christian Löwenstein

Open Mathematics (2012)

- Volume: 10, Issue: 3, page 1133-1140
- ISSN: 2391-5455

## Access Full Article

top## Abstract

top## How to cite

topMichael Henning, and Christian Löwenstein. "Hypergraphs with large transversal number and with edge sizes at least four." Open Mathematics 10.3 (2012): 1133-1140. <http://eudml.org/doc/269535>.

@article{MichaelHenning2012,

abstract = {Let H be a hypergraph on n vertices and m edges with all edges of size at least four. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 1990, 50(1), 129–133] proved that τ(H) ≤ 2(n+m)/9, while Chvátal and McDiarmid [Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26] proved that τ(H) ≤ (n + 2m)/6. In this paper, we characterize the connected hypergraphs that achieve equality in the Lai-Chang bound and in the Chvátal-McDiarmid bound.},

author = {Michael Henning, Christian Löwenstein},

journal = {Open Mathematics},

keywords = {Transversal; 4-uniform hypergraph; transversal},

language = {eng},

number = {3},

pages = {1133-1140},

title = {Hypergraphs with large transversal number and with edge sizes at least four},

url = {http://eudml.org/doc/269535},

volume = {10},

year = {2012},

}

TY - JOUR

AU - Michael Henning

AU - Christian Löwenstein

TI - Hypergraphs with large transversal number and with edge sizes at least four

JO - Open Mathematics

PY - 2012

VL - 10

IS - 3

SP - 1133

EP - 1140

AB - Let H be a hypergraph on n vertices and m edges with all edges of size at least four. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 1990, 50(1), 129–133] proved that τ(H) ≤ 2(n+m)/9, while Chvátal and McDiarmid [Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26] proved that τ(H) ≤ (n + 2m)/6. In this paper, we characterize the connected hypergraphs that achieve equality in the Lai-Chang bound and in the Chvátal-McDiarmid bound.

LA - eng

KW - Transversal; 4-uniform hypergraph; transversal

UR - http://eudml.org/doc/269535

ER -

## References

top- [1] Chvátal V., McDiarmid C., Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26 http://dx.doi.org/10.1007/BF01191201 Zbl0776.05080
- [2] Henning M.A., Yeo A., Hypergraphs with large transversal number and with edge sizes at least 3, J. Graph Theory, 2008, 59(4), 326–348 Zbl1211.05091
- [3] Lai F.C., Chang G.J., An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 1990, 50(1), 129–133 http://dx.doi.org/10.1016/0095-8956(90)90101-5
- [4] Thomassé S., Yeo A., Total domination of graphs and small transversals of hypergraphs, Combinatorica, 2007, 27(4), 473–487 http://dx.doi.org/10.1007/s00493-007-2020-3 Zbl1164.05052
- [5] Tuza Zs., Covering all cliques of a graph, Discrete Math., 1990, 86(1–3), 117–126 http://dx.doi.org/10.1016/0012-365X(90)90354-K
- [6] Yeo A., private communication

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.