Anzeige
Erschienen in:
23.11.2016
Matching and domination numbers in r-uniform hypergraphs
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2017
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A matching is a set of pairwise disjoint hyperedges of a hypergraph H. The matching number \(\nu (H)\) of H is the maximum cardinality of a matching. A subset D of vertices of H is called a dominating set of H if for every vertex v not in D there exists \(u\in D\) such that u and v are contained in a hyperedge of H. The minimum cardinality of a dominating set of H is called the domination number of H and is denoted by \(\gamma (H)\). In this paper we show that every r-uniform hypergraph H satisfies the inequality \(\gamma (H)\le (r-1)\nu (H)\) and the bound is sharp.