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) having no isolated nodes, then V - 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 (n(2)m). (C) 2015 Elsevier B.V. All rights reserved.