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

## References

top- [1] B.D. Acharya, Domination in hypergraphs, AKCE Int. J. Graphs Comb. 4 (2007) 117-126. Zbl1136.05047
- [2] B.D. Acharya, Domination in hypergraphs II. New directions, in: Proc. Int. Conf. ICDM 2008, Mysore, India, 1-16. Zbl1231.05192
- [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[Crossref] Zbl1164.05415
- [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[Crossref][WoS]
- [5] V. Chvátal and C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19-26. doi:10.1007/BF01191201[WoS][Crossref] Zbl0776.05080
- [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[Crossref] Zbl1211.05091
- [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[WoS] Zbl1245.05098
- [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[WoS][Crossref]
- [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[WoS][Crossref]
- [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[Crossref] Zbl1216.05105
- [12] B.K. Jose and Zs. Tuza, Hypergraph domination and strong independence, Appl. Anal. Discrete Math. 3 (2009) 237-358. doi:10.2298/AADM0902347J[WoS][Crossref] Zbl1199.05261
- [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[Crossref]
- [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[Crossref] Zbl1138.05055

## NotesEmbed ?

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