Trees whose double domination number is twice their domination number

摘要

In a graph G, a vertex dominates itself and its neighbors. A subset S of V is a dominating set of G if S dominates every vertex of G at least once. A subset S of V is an independent dominating set of G if 5 is a dominating set and the induced subgraph G[S] has no edges. The domination number γ(G) is the minimum cardinality of a dominating set of G. Similarly, the independent domination number I(G) is the minimum cardinality of an independent dominating set of G. A subset S C V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The double domination number dd(G) is the minimum cardinality of a double dominating set of G. In this note we first prove that for a tree T of order at least two, dd(T) = 2γ(T) if and only if γ(T) = I(T) and every dd(T)-set of T is the union of two disjoint I(T)-sets. Then, we present a constructive characterization of all trees with dd(T) = 2γ(T).