## Contributed Session Thu.2.H 3004

#### Thursday, 13:15 - 14:45 h, Room: H 3004

**Cluster 2: Combinatorial optimization** [...]

### Cycles in graphs

**Chair: Peter Recht**

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

**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.

**Thursday, 13:45 - 14:10 h, Room: H 3004, Talk 2**

**Eva-Maria Sprengel**

An optimal cycle packing for generalized Petersen graphs *P(n,k)* with *k* even

**Coauthor: Peter Recht**

**Abstract:**

For an undirected graph *G=(V,E)* a maximum cycle packing is a collection of pairwise edge-disjoint cycles. The maximum cardinality of such a packing is denoted as the cycle packing number * ν (G)*.

In general the determination of a maximum cycle packing and the cycle packing number, respectively, is NP-hard.

In this lecture we consider the family of generalized Petersen graphs *P(n,k)* with *k* even. We give a lower and an upper bound on the cycle packing number and outline the structure of one optimal cycle packing of such graphs.

**Thursday, 14:15 - 14:40 h, Room: H 3004, Talk 3**

**Lamia Aoudia**

4-cycle polytope on a graph

**Coauthor: Meziane Aider**

**Abstract:**

The aim of this work is to give a convex hull of *4*-cycle on a wider class of complete bipartite graphs.\

Given a bipartite graph *K*_{n,m}, where *|{V*_{1}}|=n and

*|{V*_{1}}|=m, *E=V*_{1} × V_{2} and a weight function *w: E → ***R**, The *minimum weighted **4*-cycle problem consist on finding a *4*-cycle *C ⊂ E* such hat *∑*_{e ∈ C}w_{e} is minimum. This problem can easily be solved in polynomial time by complete enumeration of the the *4*-cycles of *G*. For each *4*-cycle *C*, let **X**^{C} denote the incidence vector of *C* defined by: **X**^{C} (e) = 1 and **X**^{C} =0 if *e\notin C*. The *4*-cycle polytope *PC*^{4} _{n , m} is the convex hull of the incidence vectors of the *4*-cycles of *K*_{n,m}, i.e. * PC*^{4} _{n , m} = convex hull *{***X**^{C} ∈ {0,1}: C is a 4-cycle of * G }*

The minimum weighted *4*-cycle problem is clearly equivalent to the linear program * min {wx : x ∈ PC*^{4}_{n,n} }.

We are mainly interested by the facial tructure of *PC*^{4} _{n,m}. Thus, we enumerate some inequalities defining facets of *PC*^{4} _{n, n}.