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:
“... even I am growing accustomed to slavery; so much so that I cease to think of its accursed influence and calmly eat from the hands of the bondman without being mindful that he is such. O, Slavery, hateful thing that thou art thus to blunt the keen edge of conscience!”
—Susan B. Anthony (1820–1907)
“... 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)
“Ye ugly, creepin, blastit wonner,
Detested, shunn’d by saunt an’ sinner,
How dare ye set your fit upon her,
Sae fine a lady!”
—Robert Burns (1759–1796)