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:
“Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man’s appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded.”
—Abraham Lincoln (1809–1865)
“Nature seems at each man’s birth to have marked out the bounds of his virtues and vices, and to have determined how good or how wicked that man shall be capable of being.”
—François, Duc De La Rochefoucauld (1613–1680)
“Great Wits are sure to Madness near alli’d
And thin Partitions do their Bounds divide;
Else, why should he, with Wealth and Honour blest,
Refuse his Age the needful hours of Rest?”
—John Dryden (1631–1700)