A characterization of hypergraphs with large domination number

Michael A. Henning, Christian Löwenstein

Research output: Contribution to journalArticlepeer-review

2 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 ≠ φ. The domination number γ(H) is the minimum cardinality of a dominating set in H. It is known [Cs. Bujtas, M.A. Henning and Zs. Tuza, Transversals and domination in, uniform, hypergraphs, European J. Combin. 33 (2012) 62-71] that for k ≥ 5, if H is a hypergraph of order n and size m with all edges of size at least k and with no isolated vertex, then γ(H) ≤ (n+ L(k - 3)/2] m)/([3(k - 1)/2]). In this paper, we apply a recent result of the authors on hypergraphs with large transversal number [M.A. Henning and C. Löwenstein, A characterization, of hypergraphs that achieve equality in, the Chvátal-McDiarm.id Theorem, Discrete Math. 323(2014)69-75] to characterize the hypergraphs achieving equality in this bound.

Original languageEnglish
Pages (from-to)427-438
Number of pages12
JournalDiscussiones Mathematicae - Graph Theory
Volume36
Issue number2
DOIs
Publication statusPublished - 2016

Keywords

  • Domination
  • Hypergraph
  • Transversal

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A characterization of hypergraphs with large domination number'. Together they form a unique fingerprint.

Cite this