✦ LIBER ✦

Gear composition and the stable set polytope

✍ Scribed by A. Galluccio; C. Gentile; P. Ventura

Publisher: Elsevier Science
Year: 2008
Tongue: English
Weight: 414 KB
Volume: 36
Category: Article
ISSN: 0167-6377
DOI: 10.1016/j.orl.2008.01.003

No coin nor oath required. For personal study only.

✦ Synopsis

We present a new graph composition that produces a graph G from a given graph H and a fixed graph B called gear and we study its polyhedral properties. This composition yields counterexamples to a conjecture on the facial structure of STAB(G) when G is claw-free.

📜 SIMILAR VOLUMES

Coloring planar Toeplitz graphs and the

Coloring planar Toeplitz graphs and the stable set polytope

✍ Reinhardt Euler 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 290 KB

Cliques and odd cycles are well known to induce facet-deÿning inequalities for the stable set polytope. In graph coloring cliques are a class of n-critical graphs whereas odd cycles represent the class of 3-critical graphs. In the ÿrst part of this paper we generalize both notions to (Kn \ e)-cycles

Stability critical graphs and ranks face

Stability critical graphs and ranks facets of the stable set polytope

✍ E.C. Sewell; L.E. Trotter Jr. 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 616 KB

Rank inequalities due to stability critical (u-critical) graphs are used to develop a finite nested sequence of linear relaxations of the stable set polytope, the strongest of which provides an integral max-min relation: In a simple graph, the maximum size of a stable set is equal to the minimum (we

On the facets of the stable set polytope

On the facets of the stable set polytope of quasi-line graphs

✍ Gautier Stauffer 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 237 KB

Clique family inequalities for the stabl

Clique family inequalities for the stable set polytope of quasi-line graphs

✍ G. Oriolo 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 248 KB

In one of fundamental works in combinatorial optimization, Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets in its line graph. Also the neighborhood of any vertex in a line graph partitions into two cliques: graphs with this latt

On the sensitivity of von Neumann and Mo

On the sensitivity of von Neumann and Morgenstern abstract stable sets: The stable and the individual stable bargaining set

✍ J. Greenberg 📂 Article 📅 1992 🏛 Springer-Verlag 🌐 English ⚖ 789 KB

Minimal covers, minimal sets and canonic

Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope

✍ Daniel Granot; Frieda Granot 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 924 KB