## 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|. The hypergraph H is k-uniform if every edge of H has size k. Two vertices in H are adjacent if they belong to a common edge in H. A transversal in H is a subset of vertices in H that has a nonempty intersection with every edge of H. A total transversal in H is a transversal T in H with the additional property that every vertex in T is adjacent to some other vertex of T. The total transversal number τ_{t} (H) of H is the minimum cardinality of a total transversal in H. For k ≥ 2, let b_{k} = sup_{H ∈Hk} τ_{t} (H)/(n_{H} + m_{H}), where H_{k} denotes the class of all k -uniform hypergraphs containing no isolated vertices or isolated edges or multiple edges. It is known that b_{2} = 2/5, b_{3} = 1/3, b_{4} ≤ 1/3, and b_{5} ≤ 2/7. In this paper, we show that b_{4} = 2/7 and b_{6} ≤ 1/4. Further, for k ≥ 7, we show that b_{7} ≤ 2/9. These results on total transversals have applications in total domination in hypergraphs. A total dominating set in H is a subset of vertices D ⊆ V such that every vertex in H is adjacent to some vertex in D. The total domination number γ_{t} (H) is the minimum cardinality of a total dominating set in H. The following relationship between the total transversal number and the total domination number of uniform hypergraphs is known: For k ≥ 3 and H ∈ H_{k}, we have γ_{t} (H) ≤ (max { 2/k +1, b_{k-1}}) × n_{H}. As a consequence of our results on the total transversal number, for k ∈ {2, 3, 4, 5, 6, 7, 8} and a hypergraph H ∈ H_{k}, we have γ_{t} (H) ≤ 2n_{H}/(k + 1).

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

Journal | SIAM Journal on Discrete Mathematics |

Volume | 29 |

Issue number | 1 |

Pages (from-to) | 309-320 |

ISSN | 0895-4801 |

DOIs | |

Publication status | Published - 2015 |

Externally published | Yes |

## Keywords

- Hypergraph
- Total domination
- Total transversal