کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872027 | 681717 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
[1,2]-sets and [1,2]-total sets in trees with algorithms
ترجمه فارسی عنوان
[1،2] مجموعه ها و مجموعه های [1،2] کل در درخت ها با الگوریتم ها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A set SâV of the graph G=(V,E) is called a [1,2]-set of G if any vertex which is not in S has at least one but no more than two neighbors in S. A set Sâ²âV is called a [1,2]-total set of G if any vertex of G, no matter in Sâ² or not, is adjacent to at least one but not more than two vertices in Sâ². In this paper we introduce a linear algorithm for finding the cardinality of the smallest [1,2]-sets and [1,2]-total sets of a tree and extend it to a more generalized version for [i,j]-sets, a generalization of [1,2]-sets. This answers one of the open problems proposed in Chellali et al. (2013). Then since not all trees have [1,2]-total sets, we devise a recursive method for generating all the trees that do have such sets. This method also constructs every [1,2]-total set of each tree that it generates.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 136-146
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 136-146
نویسندگان
A.K. Goharshady, M.R. Hooshmandasl, M. Alambardar Meybodi,