|
Abstract
|
Given a digraph D=(V,A), a vertex set P⊆V is a packing if there are no arcs joining vertices in P and for any two vertices x,y∈P, the sets of in-neighbors of x and y are disjoint. A set S⊆V is a dominating set (or open dominating set) if every vertex in V−S (or in V) has an in-neighbor in S. A dominating set S is called a total dominating set if the subgraph induced by S has no isolated vertices. In this paper we consider maximum packing, minimum dominating, minimum open dominating and minimum total dominating sets in digraphs. We show that in directed trees, the maximum cardinality of a packing equals the minimum cardinality of a dominating set. We prove similar results for what are called contrafunctional digraphs and we characterize the class of these digraphs for which these two numbers are equal. Finally, we solve two open problems about total and open dominating sets in digraphs given in a paper by Arumugam et al. (2007)
|