Citation

L. Liptak et L. Lovasz, Critical facets of the stable set polytope, COMBINATORI, 21(1), 2001, pp. 61-88

Citations number

13

Language

INGLESE

art.tipo

Article

Categorie Soggetti

Mathematics,"Computer Science & Engineering

Journal title

COMBINATORICA

ISSN journal

0209-9683
→ ACNP

Volume

21

Issue

1

Year of publication

2001

Pages

61 - 88

Database

ISI

SICI code

0209-9683(2001)21:1<61:CFOTSS>2.0.ZU;2-R

Abstract

A facet of the stable set polytope of a graph G can be viewed as a generali
zation of the notion of an alpha -critical graph. We extend several results
from the theory of alpha -critical graphs to facets. The defect of a nontr
ivial, full-dimensional facet Sigma (v is an element ofV) a(v)x(v) less tha
n or equal to b of the stable set polytope of a graph G is defined by delta
= Sigma (v is an element ofV) a(v) - 2b. We prove the upper bound a(u) + d
elta for the degree of any node u in a critical facet-graph, and show that
d(u)= 2 delta can occur only when delta = 1. We also give a simple proof of
the characterization of critical facet-graphs with defect 2 proved by Sewe
ll [11]. As an application of these techniques we sharpen a result of Suran
yi [13] by showing that if an alpha -critical graph has defect delta and co
ntains delta + 2 nodes of degree delta + 1, then the graph is an odd subdiv
ision of Kdelta +2.