Prouvant qu'il existe un ensemble de distance à distance $ d $-dominant $ o (n / delta) $

Question

Laisser $ d> 1 $, et considérez un graphique $ G = (v, e) $ sur $ n $ sommets. UN distance $ d $-Dant dominant de $ G $ est un ensemble $ D subseseq v $ avec la propriété qui pour tout $ v in v $, Soit $ v in d $ ou $ v $ est au maximum $ d $ de certains sommets dans $ D $. Prouver que si $ delta $, le degré minimum de $ G $, satisfait $ delta> 50 $, alors $ G $ a une distance $ d $-Sant de taille dominant $ O (n / delta) $.

J'envisage un algorithme gourmand à construire $ D $. À chaque étape, choisissez un sommet qui couvre le nombre maximal de sommets "découverts" (c'est-à-dire, des sommets de distance $> d $ de n'importe quel élément dans $ D $). Pour chaque sommet $ v $, laisser $ C (v) $ être l'ensemble composé de $ v $ avec tous ces sommets qui sont au maximum $ d $ de $ v $. Supposons que pendant le processus de sélection des sommets, le nombre de sommets $ u $ qui ne résident pas dans l'union des sets $ C (v) $ des sommets choisis jusqu'à présent $ r $. Puis par hypothèse, la somme des cardinalités des ensembles $ C (u) $ sur tous les sommets découverts $ u $ Est au moins $ rx $....

L'inconvénient de cette approche est que je ne vois pas comment $ x $, une limite inférieure sur le nombre de sommets à distance $ d $ d'un sommet dans $ G $, peut être plus que $ delta + 1 $ (c'est-à-dire, l'ordre du graphique complet $ K _ { delta + 1} $). Malheureusement, si nous utilisons cette limite inférieure pour $ x $ En général, nous n'obtiendrons pas un ensemble de taille dominant $ O (n / delta) $.