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:
“The self-consciousness of Pine Ridge manifests itself at the village’s edge in such signs as “Drive Keerful,” “Don’t Hit Our Young ‘uns,” and “You-all Hurry Back”Mlocutions which nearly all Arkansas hill people use daily but would never dream of putting in print.”
—Administration in the State of Arka, U.S. public relief program (1935-1943)
“We are all hostages, and we are all terrorists. This circuit has replaced that other one of masters and slaves, the dominating and the dominated, the exploiters and the exploited.... It is worse than the one it replaces, but at least it liberates us from liberal nostalgia and the ruses of history.”
—Jean Baudrillard (b. 1929)
“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)