On the use of augmenting chains in chain packings

D. de Werra, F. S. Roberts

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


In a graph G = (X, E), we assign to each node υ a positive integer b(υ)≤dG(υ), where dG(υ) is the degree of υ in G. Let P be a collection of edge-disjoint chains such that no two chains in P have a common endpoint and such that in the partial graph H = (X, E(P)) formed by the edge set E(P) of P we have dH(υ)≤b(υ) for each node υ. P is called a chain packing. We extend the augmenting chain theorem of matchings to chain packings and we find an analogue of matching matroids. We also study chain packings by short chains, i.e., chains of lengths one or two. We show that we may restrict ourselves to packings by short chains when we want to find a packing containing a maximum number of chains. We show that the use of augmenting chains fails in general to produce a new short chain packing from an old one, even for bipartite graphs, but that it does do so for the special case of trees. For the case of trees, we also find a min-max result for packings by short chains.

Original languageEnglish (US)
Pages (from-to)137-149
Number of pages13
JournalDiscrete Applied Mathematics
Issue number2-3
StatePublished - Feb 28 1991

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'On the use of augmenting chains in chain packings'. Together they form a unique fingerprint.

Cite this