Paths, Stars and the Number Three

Source abstract

A dominating set for a graph G is a set D of vertices of G such that every vertex of G not in D is adjacent to a vertex of D . We prove that any graph G of minimum degree at least three contains a dominating set D of size at most 3| V ( G )|/8. A star S is a graph consisting of a centre x and a set of edges from x to S — x . Clearly, a dominating set D for a graph G corresponds to a set of | D | stars which cover V ( G ). Thus, we show that the vertices of any graph G of minimum degree 3 can be covered by at most 3| V ( G )|/8 vertex disjoint stars. We also show that any connected cubic graph G can be covered by [| V ( G )|/9] vertex disjoint paths. Both these results are sharp.