A Characterization of Hypergraphs with Large Domination Number

Michael 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 -