Hypergraphs with large transversal number and with edge sizes at least 3
✍ Scribed by Michael A. Henning; Anders Yeo
- Publisher
- John Wiley and Sons
- Year
- 2008
- Tongue
- English
- Weight
- 264 KB
- Volume
- 59
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
It is shown in several manuscripts [Discrete Math 86 (1990), 117–126; Combinatorica 12 (1992), 19–26] that every hypergraph of order n and size m with edge sizes at least 3 has a transversal of size at most (n + m)/4. In this article, we characterize the connected such hypergraphs that achieve equality in this bound. As a direct consequence of this bound, the total domination of a graph with minimum degree at least 3 is at most one‐half its order. An elegant graph theoretic proof of this result is presented in Archdeacon et al. [J Graph Theory 46 (2004), 207–210]. Using our hypergraph result, we characterize the connected graphs with minimum degree at least 3 and with total domination number exactly one‐half their order. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 326–348, 2008