# A Characterization of Hypergraphs with Large Domination Number

Michael A. Henning; Christian Löwenstein

Discussiones Mathematicae Graph Theory (2016)

- Volume: 36, Issue: 2, page 427-438
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMichael A. Henning, and Christian Löwenstein. "A Characterization of Hypergraphs with Large Domination Number." Discussiones Mathematicae Graph Theory 36.2 (2016): 427-438. <http://eudml.org/doc/277116>.

@article{MichaelA2016,

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. Bujtás, 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 + ⌊(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-McDiarmid Theorem, Discrete Math. 323 (2014) 69-75] to characterize the hypergraphs achieving equality in this bound.},

author = {Michael A. Henning, Christian Löwenstein},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {domination; transversal; hypergraph},

language = {eng},

number = {2},

pages = {427-438},

title = {A Characterization of Hypergraphs with Large Domination Number},

url = {http://eudml.org/doc/277116},

volume = {36},

year = {2016},

}

TY - JOUR

AU - Michael A. Henning

AU - Christian Löwenstein

TI - A Characterization of Hypergraphs with Large Domination Number

JO - Discussiones Mathematicae Graph Theory

PY - 2016

VL - 36

IS - 2

SP - 427

EP - 438

AB - 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. Bujtás, 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 + ⌊(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-McDiarmid Theorem, Discrete Math. 323 (2014) 69-75] to characterize the hypergraphs achieving equality in this bound.

LA - eng

KW - domination; transversal; hypergraph

UR - http://eudml.org/doc/277116

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.