A (simple) clutter is a family of pairwise incomparable subsets of a finite set . We say that a clutter is a domination clutter if there is at least a graph such that the collection of the inclusion-minimal dominating sets of vertices of is equal to . Given a clutter , we are interested in determining if it is a domination clutter and, if this is not the case, we want to find domination clutters in some sense close to it: the domination completions of . Here we will focus on the family of clutters containing all the subsets with the same cardinality; the uniform clutters of maximum size. Specifically, we characterize those clutters in this family that are domination clutters and, in any other case, we prove that the domination completions exist. Moreover, we then demonstrate that the clutter is uniquely determined by some of its domination completions, in the sense that can be recovered from some of these domination completions by using a suitable operation between clutters.

Peer Reviewed