کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420948 684008 2007 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Characterization of double domination subdivision number of trees
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Characterization of double domination subdivision number of trees
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 13, 15 August 2007, Pages 1700–1707
نویسندگان
, , ,