Paths, Stars and the Number Three
Bruce A. Reed · Combinatorics Probability Computing · 1996
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.