Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Edge dominating set
open-in-new
<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, an edge dominating set for a graph <i>G</i> = (<i>V</i>, <i>E</i>) is a subset <i>D</i> ⊆ <i>E</i> such that every edge not in <i>D</i> is adjacent to at least one edge in <i>D</i>. An edge dominating set is also known as a <i>line dominating set</i>. Figures (a)–(d) are examples of edge dominating sets (thick red lines). </p><p>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). </p>