Minimal vertices of 2-edge connected polyhedra

J. Fonlupt, A. Mahjoub

IBP-EC 1996/02: Rapport de Recherche EC / EC research reports
45 pages - Mars/March 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Minimal vertices of 2-edge connected polyhedra

Résumé : Dans cet article, nous étudions les points extrêmes du polytope P(G) qui est la relaxation linéaire du polytope dont les points extrêmes sont les vecteurs d'incidence des sous graphes 2-arêtes connexes de G. Nous introduisons un ordre sur les points extrêmes de P(G) et nous caractérisons les points extrêmes minimaux non entiers de ces polytopes. Ceci nous conduit à une caractérisation des graphes G pour lesquels P(G) est entier.

Abstract : In this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge connected spanning subgraph polytope of a graph G. We introduce an ordering on the extreme points of P(G), and we characterize the minimal fractional extreme points with respect to that ordering. We show that a fractional extreme point x of P(G) is minimal if and only if G can be reduced (by means of some reduction operations) to a graph belonging to a specific class of graphs. As a consequence we obtain a characterization for perfectly 2-edge connected graphs, the graphs for which P(G) is integral.

Publications internes EC 1996 / EC research reports 1996