Polyhedral consequences of the amalgam operation

✍ Scribed by M. Burlet; J. Fonlupt

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 980 KB
• Volume: 130
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)00520-2

✦ Synopsis

In a previous result concerning

Meyniel graphs, the authors defined an operation for composing graphs. This operation constructs from two graphs G1 and G2 a new graph G1 0 G2, called the amalgam of G1 and G2. If G1 and G2 are Meyniel graphs then G1 0 G2 is also a Meyniel graph. Similarly if G1 and G2 are perfect graphs then G1 0 G2 is also a perfect graph. Here we study this operation from a polyhedral point of view. Starting from descriptions of the stable set polytopes P(G,) and P(G,) associated to G1 and G2 by means of valid linear inequalities, we give a complete description of P(G1 0 G,). This result contains earlier results of this sort for the join, substitution composition, and clique join-operation. Furthermore it yields another proof that the amalgam operation preserves perfectness.