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/

[1] B.D. Acharya, Domination in hypergraphs, AKCE Int. J. Graphs Comb. 4 (2007) 117-126.

[2] B.D. Acharya, Domination in hypergraphs II. New directions, in: Proc. Int. Conf. ICDM 2008, Mysore, India, 1-16.

[3] B.D. Acharya and P. Gupta, Weak edge-degree domination in hypergraphs, Czechoslovak Math. J. 56 (131) (2006) 99-108. doi:10.1007/s10587-006-0008-6

[4] Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62-71. doi:10.1016/j.ejc.2011.08.002

[5] V. Chvátal and C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19-26. doi:10.1007/BF01191201

[6] M.A. Henning, I. Schiermeyer and A. Yeo, A new bound on the domination number of graphs with minimum degree two, Electron. J. Combin. 18 (2011) #P12.

[7] M.A. Henning and A. Yeo, Hypergraphs with large transversal number and with edge sizes at least three, J. Graph Theory 59 (2008) 326-348. doi:10.1002/jgt.20340

[8] M.A. Henning and C. Löwenstein, Hypergraphs with large domination number and edge sizes at least 3, Discrete Applied Math. 160 (2012) 1757-1765. doi:/10.1016/j.dam.2012.03.023

[9] M.A. Henning and C. Löwenstein, Hypergraphs with large transversal number and with edge sizes at least four, Cent. Eur. J. Math. 10 (2012) 1133-1140. doi:10.2478/s11533-012-0023-9

[10] 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. doi:10.1016/j.disc.2014.01.014

[11] T. Honjo, K. Kawarabayashi and A. Nakamoto, Dominating sets in triangulations on surfaces, J. Graph Theory 63 (2010) 17-30. doi:10.1002/jgt.20401

[12] B.K. Jose and Zs. Tuza, Hypergraph domination and strong independence, Appl. Anal. Discrete Math. 3 (2009) 237-358. doi:10.2298/AADM0902347J

[13] F.C. Lai and G.J. Chang, An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B 50 (1990) 129-133. doi:10.1016/0095-8956(90)90101-5

[14] C. Löwenstein and D. Rautenbach, Domination in graphs of minimum degree at least two and large girth, Graphs Combin. 24 (2008) 37-46. doi:10.1007/s00373-007-0770-8