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:
“Truth that peeps
Over the glasses’ edge when dinner’s done.”
—Robert Browning (1812–1889)
“... 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)
“But beauty is set apart,
beauty is cast by the sea,
a barren rock,
beauty is set about
with wrecks of ships....”
—Hilda Doolittle (1886–1961)