Total transversals in hypergraphs and their applications

Michael A. Henning, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review

31 Downloads (Pure)

Abstract

Let H = (V,E ) be a hypergraph with vertex set V and edge set E of order nH = | V | and size mH = |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 bk = supH ∈Hk τt (H)/(nH + mH), where Hk denotes the class of all k -uniform hypergraphs containing no isolated vertices or isolated edges or multiple edges. It is known that b2 = 2/5, b3 = 1/3, b4 ≤ 1/3, and b5 ≤ 2/7. In this paper, we show that b4 = 2/7 and b6 ≤ 1/4. Further, for k ≥ 7, we show that b7 ≤ 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 ∈ Hk, we have γt (H) ≤ (max { 2/k +1, bk-1}) × nH. As a consequence of our results on the total transversal number, for k ∈ {2, 3, 4, 5, 6, 7, 8} and a hypergraph H ∈ Hk, we have γt (H) ≤ 2nH/(k + 1).

Original languageEnglish
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number1
Pages (from-to)309-320
ISSN0895-4801
DOIs
Publication statusPublished - 2015
Externally publishedYes

Keywords

  • Hypergraph
  • Total domination
  • Total transversal

Fingerprint

Dive into the research topics of 'Total transversals in hypergraphs and their applications'. Together they form a unique fingerprint.

Cite this