Bounds
Let G be a graph with n ≥ 1 vertices and let Δ be the maximum degree of the graph. The following bounds on γ(G) are known (Haynes, Hedetniemi & Slater 1998a, Chapter 2):
- One vertex can dominate at most Δ other vertices; therefore γ(G) ≥ n/(1 + Δ).
- The set of all vertices is a dominating set in any graph; therefore γ(G) ≤ n.
If there are no isolated vertices in G, then there are two disjoint dominating sets in G; see domatic partition for details. Therefore in any graph without isolated vertices it holds that γ(G) ≤ n/2.
Read more about this topic: Dominating Set
Famous quotes containing the word bounds:
“Firmness yclept in heroes, kings and seamen,
That is, when they succeed; but greatly blamed
As obstinacy, both in men and women,
Whene’er their triumph pales, or star is tamed —
And ‘twill perplex the casuist in morality
To fix the due bounds of this dangerous quality.”
—George Gordon Noel Byron (1788–1824)
“What comes over a man, is it soul or mind
That to no limits and bounds he can stay confined?
You would say his ambition was to extend the reach
Clear to the Arctic of every living kind.
Why is his nature forever so hard to teach
That though there is no fixed line between wrong and right,
There are roughly zones whose laws must be obeyed?”
—Robert Frost (1874–1963)
“How far men go for the material of their houses! The inhabitants of the most civilized cities, in all ages, send into far, primitive forests, beyond the bounds of their civilization, where the moose and bear and savage dwell, for their pine boards for ordinary use. And, on the other hand, the savage soon receives from cities iron arrow-points, hatchets, and guns, to point his savageness with.”
—Henry David Thoreau (1817–1862)