Bounds related to domination in graphs with minimum degree two
Laura A. Sanchis · Journal of Graph Theory · 1997
A dominating set for a graph G = (V,E) is a subset of vertices V′ ⊆ V such that for all v E V − V′ there exists some u E V′ for which {v, u} E E. The domination number of G is the size of its smallest dominating set(s). We show that for almost all connected graphs with minimum degree at least 2 and q edges, the domination number is bounded by (q + 1)/3. From this we derive exact lower bounds for the number of edges of a connected graph with minimum degree at least 2 and a given domination number. We also generalize the bound to k-restricted domination numbers; these measure how many vertices are necessary to dominate a graph if an arbitrary set of k vertices must be incluced in the dominating set. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 139–152, 1997