Geodesic
A Characterization of Hypergraphs with Large Domination Number
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 427-438

Voir la notice de l'article provenant de la source Library of Science

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 for which v ∈ℯ and ℯ∩ 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.
Keywords: domination, transversal, hypergraph 
@article{DMGT_2016_36_2_a13,
     author = {Henning, Michael A. and L\"owenstein, Christian},
     title = {A {Characterization} of {Hypergraphs} with {Large} {Domination} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {427--438},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a13/}
}
TY  - JOUR
AU  - Henning, Michael A.
AU  - Löwenstein, Christian
TI  - A Characterization of Hypergraphs with Large Domination Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 427
EP  - 438
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a13/
LA  - en
ID  - DMGT_2016_36_2_a13
ER  - 
%0 Journal Article
%A Henning, Michael A.
%A Löwenstein, Christian
%T A Characterization of Hypergraphs with Large Domination Number
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 427-438
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a13/
%G en
%F DMGT_2016_36_2_a13
Henning, Michael A.; Löwenstein, Christian. A Characterization of Hypergraphs with Large Domination Number. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 427-438. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a13/