Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420948 | Discrete Applied Mathematics | 2007 | 8 Pages |
In a graph G, a vertex dominates itself and its neighbors. A subset S⊆V(G)S⊆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)dd(G) is the minimum cardinality of a double dominating set of G. The double domination subdivision number sddd(G)sddd(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the double domination number. In this paper first we establish upper bounds on the double domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that sddd(G)⩽3sddd(G)⩽3. We also prove that 1⩽sddd(T)⩽21⩽sddd(T)⩽2 for every tree T, and characterize the trees T for which sddd(T)=2sddd(T)=2.