Polyhedral consequences of the amalgam operation (Q1331977): Difference between revisions

The authors consider the amalgam \(G_ 1\varnothing G_ 2\) of two graphs \(G_ 1\) and \(G_ 2\) which has the property that if \(G_ 1\) and \(G_ 2\) are Meyniel graphs then their amalgam is also a Meyniel graph, and a similar conclusion holds for perfect graphs. In this paper this operation is studied from a polyhedral point of view. Using descriptions of the stable set polytopes \(P(G_ 1)\) and \(P(G_ 2)\) by means of valid linear inequalities, a complete description of \(P(G_ 1\varnothing G_ 2)\) is given. This result generalizes earlier results of a similar nature for other graph operations.