کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420948 | 684008 | 2007 | 8 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Applied Mathematics - Volume 155, Issue 13, 15 August 2007, Pages 1700–1707