**Thursday, 13:15 - 13:40 h, Room: H 3004**

**Peter Recht**

A "min-max-theorem'' for the cycle packing problem in Eulerian graphs

**Coauthor: Eva-Maria Sprengel**

**Abstract:**

This lecture deals with the problem to determine a set \ * ***Z**^{*}= {C_{1}, C_{2}, … , C_{ ν (G)} } of edge-disjoint cycles of maximum cardinality * ν (G)* in a graph *G=(V,E)*. The problem is tackled by considering special subgraphs: \ for a vertex *v ∈ V*, let *T(v)* be a *local trace* at *v*, i.e. *T(v)* is an Eulerian subgraph of *G* such that every walk *W(v)*, with start vertex *v* can be extended to an Eulerian tour in *T(v)*. \ In general, maximal local traces are not uniquely defined but their packing numbers * ν (T(v))* are. \ We prove that if *G* is is Eulerian every maximum edge-disjoint cycle packing **Z**^{*} of *G* induces maximum local traces *T(v)* at *v* for every *v ∈ V*. In the opposite, if the total size *∑*_{v ∈ V} |E(T(v)| is minimal then the set of induced edge-disjoint cycles in *G* must be maximum. \ The determination of such a maximal trace leads to a multi-commodity flow-problem with quadratic objective function.

Talk 1 of the contributed session Thu.2.H 3004

**"Cycles in graphs"** [...]

Cluster 2

**"Combinatorial optimization"** [...]