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

Abstract

top
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.

How to cite

top

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 -

References

top
  1. [1] B.D. Acharya, Domination in hypergraphs, AKCE Int. J. Graphs Comb. 4 (2007) 117-126. Zbl1136.05047
  2. [2] B.D. Acharya, Domination in hypergraphs II. New directions, in: Proc. Int. Conf. ICDM 2008, Mysore, India, 1-16. Zbl1231.05192
  3. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.