- Tytuł:
- A Characterization of Hypergraphs with Large Domination Number
- Autorzy:
-
Henning, Michael A.
Löwenstein, Christian - Powiązania:
- https://bibliotekanauki.pl/articles/31340924.pdf
- Data publikacji:
- 2016-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
domination
transversal
hypergraph - Opis:
- 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 \subseteq V $ such that for every vertex $ v \in V \ \backslash \ D $ there exists an edge $ \mathcal{e} \in E $ for which $ v \in \mathcal{e} $ and $ \mathcal{e} \cap D \ne \emptyset $. The domination number $ \gamma (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 \ge 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 $ \gamma (H) \ge (n + \floor{ (k − 3)//2 } m) // ( \floor{ 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 427-438
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł