The k ‐piece packing problem

A k ‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k . We consider the problem of covering the maximum number of nodes of a graph by node disjoint k ‐pieces. When k  = 1 this is the maximum matching problem, and when k  = 2 this is the problem, recently studied by Kaneko [19[, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory