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

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

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

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

Cluster 2

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