Packing non-zero $A$-paths in group-labelled graphs

M. Chudnovsky, J.F. Geelen, A.M.H. Gerards, L. Goddyn, M. Lohman, P.D. Seymour

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

55 Citaten (Scopus)

Samenvatting

Let G=(V,E) be an oriented graph whose edges are labelled by the elements of a group G and let A¿V. An A-path is a path whose ends are both in A. The weight of a path P in G is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in P. (If G is not abelian, we sum the labels in their order along the path.) We are interested in the maximum number of vertex-disjoint A-paths each of non-zero weight. When A = V this problem is equivalent to the maximum matching problem. The general case also includes Mader's S-paths problem. We prove that for any positive integer k, either there are k vertex-disjoint A-paths each of non-zero weight, or there is a set of at most 2k -2 vertices that meets each of the non-zero A-paths. This result is obtained as a consequence of an exact min-max theorem.
Originele taal-2Engels
Pagina's (van-tot)521-532
TijdschriftCombinatorica
Volume26
Nummer van het tijdschrift5
DOI's
StatusGepubliceerd - 2006

Vingerafdruk

Duik in de onderzoeksthema's van 'Packing non-zero $A$-paths in group-labelled graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit