Dimostrando che esiste una distanza $ d $ -domining set di dimensioni $ o (n/ delta) $

Question

Permettere $ d> 1 $, e considera un grafico $ G = (v, e) $ Su $ n $ vertici. UN distanza $ d $-Mant set di $ G $ è un set $ D sottoseteq v $ con la proprietà che per qualsiasi $ v in v $, o $ v in d $ o $ V $ è al massimo distanza $ d $ da qualche vertice in $ D $. Dimostra che se $ Delta $, il grado minimo di $ G $, soddisfa $ Delta> 50 $, poi $ G $ ha una distanza $ d $-Sominante set di dimensioni $ O (n/ Delta) $.

Sto prendendo in considerazione un algoritmo avido da costruire $ D $. In ogni passaggio, scegli un vertice che copre il numero massimo di vertici "scoperti" (cioè vertici di distanza $> d $ da qualsiasi elemento in $ D $). Per ogni vertice $ V $, permettere $ C (v) $ essere il set composto da $ V $ insieme a tutti quei vertici che hanno la massima distanza $ d $ da $ V $. Supponiamo che durante il processo di raccolta dei vertici il numero di vertici $ u $ che non si trovano nell'unione dei set $ C (v) $ dei vertici scelti finora è $ r $. Quindi, per assunzione, la somma dei cardinali dei set $ C (u) $ su tutti i vertici scoperti $ u $ è almeno $ rx $....

Lo svantaggio di questo approccio è che non vedo come $ x $, un limite inferiore sul numero di vertici a distanza $ d $ di un vertice in $ G $, può essere più di $ Delta + 1 $ (cioè, l'ordine del grafico completo $ K _ { delta + 1} $). Sfortunatamente, se usiamo questo limite inferiore per $ x $ In generale, non otterremo una serie di dimensioni dominanti $ O (n/ Delta) $.