Pairs of disjoint dominating sets and the minimum degree of graphs

Löwenstein, Christian; Rautenbach, Dieter GND

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 \mid D_1 \cup D_2 \mid \leq \frac{6}{7} n unless G = C_4, and, if \delta \geq 5, then \mid D_1 \cup D_2 \mid \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:

Löwenstein, Christian / Rautenbach, Dieter: Pairs of disjoint dominating sets and the minimum degree of graphs. 2008.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export