This paper provides a complete characterization of the rank facets of the stable set polytope STAB(G) associated with a claw-free graph G. In particular, it is shown that a claw-free graph G produces a rank facet of STAB(G) if and only if it can be obtained by means of two simple lifting procedures from three basic classes of graphs: (i) cliques, (ii) line graphs of minimal 2-connected hypomatchable graphs, and (iii) circulant graphs C-alpha omega+1(omega-1). As a by-product, a characterization of the rank facets of STAB(G) having right-hand side 2 is given.
The rank facets of the stable set polytope for claw-free graphs
Galluccio A;
1997
Abstract
This paper provides a complete characterization of the rank facets of the stable set polytope STAB(G) associated with a claw-free graph G. In particular, it is shown that a claw-free graph G produces a rank facet of STAB(G) if and only if it can be obtained by means of two simple lifting procedures from three basic classes of graphs: (i) cliques, (ii) line graphs of minimal 2-connected hypomatchable graphs, and (iii) circulant graphs C-alpha omega+1(omega-1). As a by-product, a characterization of the rank facets of STAB(G) having right-hand side 2 is given.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
