Polyhedral consequences of the amalgam operation
type: Item
instance of: scholarly article
title: Polyhedral consequences of the amalgam operation
zbMATH Open document ID: 0817.05066
DOI: 10.1016/0012-365X(92)00520-2
published in: Discrete Mathematics
publication date: 1994-08-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 626318
zbMATH Keywords: amalgam
zbMATH Keywords: Meyniel graph
zbMATH Keywords: perfect graphs
zbMATH Keywords: stable set polytopes
author: Michel Burlet
author: Jean Fonlupt
reviewed by: Maciej M. Sysło
MaRDI profile type: Publication
cites work: Q3222223
cites work: Q3222886
cites work: On certain polytopes associated with graphs
cites work: Compositions for perfect graphs
cites work: Polyhedra for Composed Independence Systems
cites work: On the facial structure of set packing polyhedra
cites work: Q3818127
description: scientific article; zbMATH DE number 626318