کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650714 | 1342499 | 2006 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A degree bound on decomposable trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A n -vertex graph is said to be decomposable if for any partition (λ1,…,λp)(λ1,…,λp) of the integer n , there exists a sequence (V1,…,Vp)(V1,…,Vp) of connected vertex-disjoint subgraphs with |Vi|=λi|Vi|=λi. In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 5, 28 March 2006, Pages 469–477
Journal: Discrete Mathematics - Volume 306, Issue 5, 28 March 2006, Pages 469–477
نویسندگان
Dominique Barth, Hervé Fournier,