Facets with fixed defect of the stable set polytope

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.