Hypergraphs with large domination number and with edge sizes at least three

Michael A. Henning, Christian Löwenstein

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

Abstract

Let H=(V,E) be a hypergraph with vertex set V and edge set E. A dominating set in H is a subset of vertices D⊆V such that for every vertex v∈V\D there exists an edge e∈E for which v∈e and e∩D≠Combining long solidus overlay. The domination number γ(H) is the minimum cardinality of a dominating set in H. It is known that if H is a hypergraph of order n with edge sizes at least three and with no isolated vertex, then γ(H)≤n3. In this paper, we characterize the hypergraphs achieving equality in this bound.

Original languageEnglish
Pages (from-to)1757-1765
Number of pages9
JournalDiscrete Applied Mathematics
Volume160
Issue number12
DOIs
Publication statusPublished - Aug 2012

Keywords

  • Domination
  • Hypergraph
  • Transversal

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Hypergraphs with large domination number and with edge sizes at least three'. Together they form a unique fingerprint.

Cite this