In graph theory, an edge dominating set for a graph G = (V, E) is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An edge dominating set is also known as a line dominating set. Figures (a)–(d) are examples of edge dominating sets (thick red lines).
A minimum edge dominating set is a smallest edge dominating set. Figures (a) and (b) are examples of minimum edge dominating sets (it can be checked that there is no edge dominating set of size 2 for this graph).
Read more about Edge Dominating Set: Properties, Algorithms and Computational Complexity
Famous quotes containing the words edge, dominating and/or set:
“Dragging out life to the last possible second is not living to the best effect. The nearer the bone, the sweeter the meat. The best of life, Passworthy, lies nearest to the edge of death.”
—H.G. (Herbert George)
“... the selfishness that is bred of great success is our shame. We have subdued the wilderness and made it ours. We have conquered the earth and the richness thereof. We have indelibly stamped upon its face the seal of our dominating will. Now, unlike Alexander sighing for more worlds to conquer, we should address ourselves to adding beauty to that glory and grandeur.”
—Alice Foote MacDougall (1867–1945)
“A more secret, sweet, and overpowering beauty appears to man when his heart and mind open to the sentiment of virtue. Then he is instructed in what is set above him. He learns that his being is without bound; that to the good, to the perfect, he is born, low as he now lies in evil and weakness.”
—Ralph Waldo Emerson (1803–1882)