Pairs of Disjoint Dominating Sets and the Minimum Degree of Graphs |
| |
Authors: | Christian Löwenstein Dieter Rautenbach |
| |
Affiliation: | 1. Institut für Mathematik, TU Ilmenau, Postfach 100565, 98684, Ilmenau, Germany
|
| |
Abstract: | 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 ${|D_1cup D_2|leq frac{6}{7}n}$ unless G = C 4, and, if δ ≥ 5, then ${|D_1cup D_2|leq 2frac{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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|