## Abstract

Let H=(V,E) be a hypergraph with vertex set V and edge set E of order n_{H}=V and size m_{H}=E. A transversal in H is a subset of vertices in H that 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 dominating set in H is a subset of vertices DV such that for every vertex vVD there exists an edge eE for which ve and eD. The domination number γ(H) is the minimum cardinality of a dominating set in H. A hypergraph H is k-uniform if every edge of H has size k. We establish the following relationship between the transversal number and the domination number of uniform hypergraphs. For any two nonnegative reals a and b and for every integer k3 the equality sup_{H∈Hkγ}(H)/(an_{H}+bm_{H})=sup_{H∈Hk-1}(H)/(an_{H}+(a+b)m_{H}) holds, where H_{k} denotes the class of all k-uniform hypergraphs containing no isolated vertices. As a consequence of this result, we establish upper bounds on the domination number of a k-uniform hypergraph with minimum degree at least 1. In particular, we show that if k≥3, then γ(H)(n_{H}+⌊k-3/2⌋m_{H})/⌊3(k-1)/2⌋ for all H∈H_{k}, and this bound is sharp. More generally, for k=2 and k=3 we prove that all the essential upper bounds can be written in the unified form γ(H)≤(an_{H}+bm_{H})/(ak+b) for constants b0 and a>-b/k.

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

Pages (from-to) | 62-71 |

Number of pages | 10 |

Journal | European Journal of Combinatorics |

Volume | 33 |

Issue number | 1 |

DOIs | |

Publication status | Published - Jan 2012 |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics