کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649374 | 1342451 | 2009 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Edge decompositions into two kinds of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let HH be an arbitrary graph and let K1,2K1,2 be the 2-edge star. By a {K1,2,H}{K1,2,H}-decomposition of a graph GG we mean a partition of the edge set of GG into subsets inducing subgraphs isomorphic to K1,2K1,2 or HH. Let JJ be an arbitrary connected graph of odd size. We show that the problem to decide if an instance graph GG has a {K1,2,H}{K1,2,H}-decomposition is NP-complete if HH has a component of an odd size and H≠pK1,2∪qJH≠pK1,2∪qJ, where pK1,2∪qJpK1,2∪qJ is the disjoint union of pp copies of K1,2K1,2 and qq copies of JJ. Moreover, we prove polynomiality of this problem for H=qJH=qJ.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 22, 28 November 2009, Pages 6368–6374
Journal: Discrete Mathematics - Volume 309, Issue 22, 28 November 2009, Pages 6368–6374
نویسندگان
Zbigniew Lonc, Monika Pszczoła,