Find in Library

<p class="p1">A subset <em>D</em> ⊆ <em>V</em>(<em>G</em>) is called an equitable dominating set of a graph <em>G</em> if every vertex <em>v</em> ∈ <em>V</em>(<em>G</em>) \ <em>D</em> has a neighbor <em>u </em>∈<em> D</em> such that |<em>d_G</em>(<em>u</em>)-<em>d_G</em>(<em>v</em>)| ≤ 1. An equitable dominating set <em>D</em> is a degree equitable restrained double dominating set (DERD-dominating set) of <em>G</em> if every vertex of <em>G</em> is dominated by at least two vertices of <em>D</em>, and 〈<em>V</em>(<em>G</em>) \ <em>D</em>〉 has no isolated vertices. The DERD-domination number of <em>G</em>, denoted by <em>γ_cl</em>^{^<em>e</em>}(<em>G</em>), is the minimum cardinality of a DERD-dominating set of <em>G</em>. We initiate the study of DERD-domination in graphs and we obtain some sharp bounds. Finally, we show that the decision problem for determining <em>γ_cl</em>^{^<em>e</em>}(<em>G</em>) is NP-complete.</p>