A set of vertices of an oriented graph is dominating if every vertex outside the set receives an arc from it. The domination hypergraph has the inclusion-minimal dominating sets as its edges. We prove Sonntag and Teichert's conjecture that the domination hypergraph of any tournament has at most one nontrivial connected component. Equivalently, after isolated vertices are discarded, the hypergraph is connected. Original conjecture, p. 182
The tournament case
For a vertex , write for its closed in-neighbourhood. Let be the inclusion-minimal members of the family of all , and let be the family of inclusion-minimal dominating sets. A set dominates precisely when it meets every member of . Conversely, a set meets every member of precisely when it contains some . Indeed, if it contains none, its complement meets every and therefore contains a minimal dominating set. It follows that is also the family of minimal sets meeting every member of .
Suppose there are two nontrivial components of the domination hypergraph. A singleton dominating set would consist of a source that beats every other vertex, so every dominating set would contain that source and would have just the singleton edge. Thus all edges of have size at least two.
Split the vertex set into two sides so each edge of belongs to a side and both sides contain an edge. Let be the minimal sets meeting every edge on side , and the corresponding sets on side . A minimal set meeting all edges is exactly the union of a minimal choice from each side. Therefore
Both and are at least two. For example, if were the sole minimal choice on side , each singleton with would meet every member of and be a dominating set.
For each pair let be a vertex with . The vertices are distinct. A row can contain at most one representative from . Two such representatives would belong to each other's closed in-neighbourhoods, forcing opposite arcs between them. A column likewise contains at most one representative from . Each representative belongs to its row set or its column set, so
As , we have . The sets are disjoint, since any common vertex would meet every member of and dominate by itself. The same applies to . Now and are disjoint. In a tournament the closed in-neighbourhoods of two vertices always intersect, since the tail of the arc between them belongs to both. This proves the conjecture.
Disconnected domination hypergraphs of oriented graphs
Allow pairs with no arc, retaining the rule that a pair cannot carry opposite arcs. We show that the domination hypergraph on its nonisolated vertices is either connected or the disjoint union of two stars, and every such union occurs. A single edge counts as a star.
The proof up to the disjointness of applies to an arbitrary oriented graph. A set meets all four members of exactly when it meets both or both . Thus the domination hypergraph consists of the complete bipartite graphs with parts and , together with isolated vertices.
Equality in forces each row to have exactly one representative from its row set and each column exactly one from its column set. After relabelling, write the four representatives as
For , the arcs from to and exclude those two representatives from . The only member of avoiding both is , which must therefore lie in . Likewise, every nonrepresentative in has in its closed in-neighbourhood. If both and had a nonrepresentative, the two would have arcs in both directions. Thus one of is a singleton. Applying the argument to shows that one of them is also a singleton.
For the converse, start with any four disjoint nonempty sets with a singleton in each pair of parts. Designate the four representatives as above and give each exactly its prescribed closed in-neighbourhood. The arcs between representatives form the directed cycle . For other vertices prescribe predecessors by the following table.
| Vertex belongs to | Required predecessors |
|---|---|
For a nonrepresentative , the required predecessors exclude the two representatives to which sends arcs. The only possible opposite-arc conflicts between nonrepresentatives would require one in each of or one in each of . The singleton assumptions exclude both. Use only the prescribed arcs. Any extra isolated vertices of the domination hypergraph can be realized by adding vertices that receive arcs from every vertex in the four parts. Each closed in-neighbourhood then contains some , and all four of these incomparable sets occur exactly. The resulting domination hypergraph has the two desired stars.