Domination equivalence in graphs (Q2369388)

A DE-pair (domination-equivalent pair) consists of two disjoint subsets of vertices with the same closed neighborhood. Likewise, an ODE-pair (open domination-equivalent pair) consists of two disjoint subsets of vertices with the same open neighborhood. One may think of an ODE-pair as a partial coloring of the vertices with red and blue, such that every vertex that has a red neighbor also has a blue neighbor, and vice versa. There is a similar interpretation for DE-pairs. The paper considers the question of determining the smallest and largest subsets over all such pairs. It provides sharp bounds on these for general graphs and for trees, and shows that the associated parameters are computable for trees but intractable in general.