Pairs of disjoint dominating sets and the minimum degree of graphs

摘要

For a connected graph G of order n and minimum degree δ we prove the existence of two disjoint dominating sets D_1 and D_2 such that, if δ ≥ 2, then, unless G = C_4, and, if δ ≥ 5, then. While for the first estimate there are exactly six extremal graphs which are all of order 7, the second estimate is asymptotically best-possible.