Chain Packings and Odd Subtree Packings
Garth Isaak · 1992
A chain packing H in a graph is a subgraph satisfying given degree constraints at the vertices. Its size is the number of odd degree vertices in the subgraph. An odd subtree packing is a chain packing which is a forest in which all non-isolated vertices have odd degree in the forest. We show that for a given graph and degree constraints, the size of a maximum chain packing and a maximum odd subtree packing are the same but the same does not hold for a version in which the sum of given weights on the odd degree vertices is to be maximized. We also note a reduction to weighted capacitated b-matching for finding a maximum size chain packing, maximum size odd subtree packing and maximum weight chain packing. The main result of this note is the proof that a min-max formula generalizing the Berge-Tutte formula for matching holds for chain packing. 1