概率论 (Summer 2013)/Problem Set 3

Problem 1

A set of vertices [math]\displaystyle{ D\subseteq V }[/math] of graph [math]\displaystyle{ G(V,E) }[/math] is a dominating set if for every [math]\displaystyle{ v\in V }[/math], either [math]\displaystyle{ v\in D }[/math] or [math]\displaystyle{ u\in D }[/math] where [math]\displaystyle{ u }[/math] is a neighbour of [math]\displaystyle{ v }[/math]. The problem of computing minimum dominating set is NP-hard. Prove that for every [math]\displaystyle{ d }[/math]-regular graph with [math]\displaystyle{ n }[/math] vertices, there exists a dominating set with size at most [math]\displaystyle{ \frac{n(1+\ln(d+1))}{d+1} }[/math].