## Abstract

Abstract: In [9] Thomassé and Yeo pose the following problem: Find the minimum c_{k} for which every k-uniform hypergraph with n vertices and n edges has a transversal of size at most c_{k}n. A direct consequence of this result is that every graph of order n with minimum degree at least k has a total dominating set of cardinality at most c_{k}n. It is known that c_{2} = 2/3, c_{3} = 1/2, and c_{4} = 3/7. Thomassé and Yeo show that 4/11 ≤ c_{5} and conjecture that c_{5} = 4/11. In this paper we show that c_{5} ≤ 17/44. Thus, 16/44 ≤ c_{5} ≤ 17/44. More generally we prove that every 5-uniform hypergraph on n vertices and m edges has a transversal with no more than (10n+7m)/44 vertices. Consequently, every graph on n vertices with minimum degree at least five has total domination number at most 17n/44.

Original language | English |
---|---|

Pages (from-to) | 155-180 |

Number of pages | 26 |

Journal | Quaestiones Mathematicae |

Volume | 38 |

Issue number | 2 |

DOIs | |

Publication status | Published - 4 Mar 2015 |

## Keywords

- Transversal
- hypergraph
- total domination in graphs

## ASJC Scopus subject areas

- Mathematics (miscellaneous)