A Characterization of Hypergraphs with Large Domination Number

• Autorzy: Michael A. Henning , Christian Löwenstein
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

domination; transversal; hypergraph

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 2
• Strony: 427-438

Daty

wydano

2016-05-01

otrzymano

2014-12-18

poprawiono

2015-08-09

zaakceptowano

2015-08-09

online

2016-04-15

Twórcy

autor

Michael A. Henning

• Department of Pure and Applied Mathematics University of Johannesburg Auckland Park, 2006, South Africa

autor

Christian Löwenstein

• Department of Pure and Applied Mathematics University of Johannesburg Auckland Park, 2006, South Africa
• Institute of Optimization and Operations Research Ulm University Ulm 89081, Germany

Identyfikatory

DOI

10.7151/dmgt.1865