A new look at the concept of domination in hypergraphs

Abstract

In this paper we propose a new definition of domination in hypergraphs in such a way that when restricted to graphs it is the usual domination in graphs. Let H = (V,E) be a hypergraph. A subset S of V is called a dominating set of H if for every vertex v in V -S, there exists an edge e ∈ E such that v ∈ e and e-{v}⊆ S. The minimum cardinality of a dominating set of H is called the domination number of H and is denoted by γ(H). We determine the domination number for several classes of uniform hypergraphs. We characterise minimal dominating sets and introduce the concept of independence and irredundance leading to domination chain in hypergraphs.