Double Domination Stable Graphs Upon Edge Removal

Document Type

Article

Publication Date

6-10-2010

Description

In a graph G = (V(G),E(G)), a vertex dominates itself and its neighbors. A subset S of V(G) is a double dominating set if every vertex of V(G) is dominated at least twice by the vertices of S. The double domination number of G is the minimum cardinality among all double dominating sets of G. We consider the effects of edge removal on the double domination number of a graph. We give a necessary and sufficient condition for a graph to have the property that the double domination number is unchanged upon the removal of any edge. Then we give a constructive characterization of trees having this property for every non-pendant edge.

Share

COinS