Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649374 | Discrete Mathematics | 2009 | 7 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zbigniew Lonc, Monika Pszczoła,