A theorem of Ore and self-stabilizing algorithms for disjoint minimal dominating sets

A theorem of Ore [20] states that if D   is a minimal dominating set in a graph G=(V,E)G=(V,E) having no isolated nodes, then V−DV−D is a dominating set. It follows that such graphs must have two disjoint minimal dominating sets R and B. We describe a self-stabilizing algorithm for finding such a pair of sets. It also follows from Ore's theorem that in a graph with no isolates, one can find disjoint sets R and B where R is maximal independent and B is minimal dominating. We describe a self-stabilizing algorithm for finding such a pair. Both algorithms are described using the Distance-2 model, but can be converted to the usual Distance-1 model [7], yielding running times of O(n2m)O(n2m).