PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

Discussiones Mathematicae Graph Theory

2016 | 36 | 2 | 427-438
Tytuł artykułu

A Characterization of Hypergraphs with Large Domination Number

Autorzy
Treść / Zawartość
Warianty tytułu
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
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
427-438
Opis fizyczny
Daty
wydano
2016-05-01
otrzymano
2014-12-18
poprawiono
2015-08-09
zaakceptowano
2015-08-09
online
2016-04-15
Twórcy
autor
• Department of Pure and Applied Mathematics University of Johannesburg Auckland Park, 2006, South Africa, mahenning@uj.ac.za
autor
• Department of Pure and Applied Mathematics University of Johannesburg Auckland Park, 2006, South Africa, christian.loewenstein@uni-ulm.de
• Institute of Optimization and Operations Research Ulm University Ulm 89081, Germany
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory