Critical extreme points of the 2-edge connected spanning subgraph polytope |
| |
Authors: | Jean Fonlupt A Ridha Mahjoub |
| |
Institution: | (1) équipe Combinatoire, UFR 921, Université Pierre et Marie Curie, 4 place Jussieu, 75252 Paris Cedex 05, France;(2) LIMOS, CNRS UMR 6158, Université Blaise Pascal Clermont II, Complexe Scientifique des Cézeaux, 63177 Aubière Cedex, France |
| |
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 a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if is a non-integer minimal extreme point of P(G), then G and can be reduced, by means of some reduction operations, to a graph G' and an extreme point of P(G') where G' and satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge connected graphs, the
graphs for which the polytope P(G) is integral.
Received: May, 2004
Part of this work has been done while the first author was visiting the Research Institute for Discrete Mathematics, University
of Bonn, Germany. |
| |
Keywords: | Polytope Cut 2-edge connected graph Critical extreme point |
本文献已被 SpringerLink 等数据库收录! |
|