Bounds related to domination in graphs with minimum degree two

✍ Scribed by Sanchis, Laura A.

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 157 KB
• Volume: 25
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199706)25:2<139::aid-jgt6>3.0.co;2-n

✦ Synopsis

A dominating set for a graph G = (V, E) is a subset of vertices V ⊆ V such that for all v ∈ V -V there exists some u ∈ V for which {v, u} ∈ 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 included in the dominating set.