Citation

L. Liptak et L. Lovasz, Facets with fixed defect of the stable set polytope, MATH PROGR, 88(1), 2000, pp. 33-44

Citations number

19

Language

INGLESE

art.tipo

Article

Categorie Soggetti

Mathematics

Journal title

MATHEMATICAL PROGRAMMING

ISSN journal

0025-5610
→ ACNP

Volume

88

Issue

1

Year of publication

2000

Pages

33 - 44

Database

ISI

SICI code

0025-5610(200006)88:1<33:FWFDOT>2.0.ZU;2-Q

Abstract

The stable set polytope of a graph is the convex hull of the 0-1 vectors co
rresponding to stable sets of vertices. To any nontrivial facet Sigma(v is
an element of V) a(v)x(v) less than or equal to b of this polytope we assoc
iate an integer delta, called the defect of the facet, by delta = Sigma(v i
s an element of V) a(v) - 2b. We show that for any fixed delta there is a f
inite collection of graphs (called "basis") such that any graph with a face
t of defect delta contains a subgraph which can be obtained from one of the
graphs in the basis by a simple subdivision operation.