If G = (V, E) is an undirected graph, a subset D of V is called a dominating set if for all v ∈ V, either v ∈ D or v is adjacent to a vertex in D. If D is a dominating set and no proper subset of D has this property, then D is called minimal. The size of any smallest dominating set in G is denoted by γ (G) and is called the domination number of G.
(a) If G has no isolated vertices, prove that if D is a minimal dominating set, then V - D is a dominating set.
(b) If I ⊆ V is independent, prove that I is a dominating set if and only if I is maximal independent.
(c) Show that γ(G) ≤β(G), and that |V| ≤β(G)x(G). [Here (G) is the independence number of G - first given in Exercise 25 of Section 11.5.]