Pairs of disjoint dominating sets and the minimum degree of graphs

For a connected graph G of order n and minimum degree \delta we prove the existence of two disjoint dominating sets D_1 and D_2 such that, if \delta\geq 2, then |D_1\cup D_2|\leq \frac{6}{7}n unless G=C_4, and, if \delta\geq 5, then |D_1\cup D_2|\leq 2\frac{1+\ln(\delta+1)}{\delta+1}n. While for the first estimate there are exactly six extremal graphs which are all of order 7, the second estimate is asymptotically best-possible.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten