Article ID Journal Published Year Pages File Type
4649374 Discrete Mathematics 2009 7 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,