Gear Composition of Stable Set Polytopes and G-Perfection

• 成果类型: Article
• 署名作者: Galluccio, Anna; Gentile, Claudio; Ventura, Paolo
• 署名单位: Consiglio Nazionale delle Ricerche (CNR)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1090.0407
• 发表日期: 2009
• 页码: 813-836
• 关键词: claw-free graphs

摘要

Graphs obtained by applying the gear composition to a given graph H are called geared graphs. We show how a linear description of the stable set polytope STAB(G) of a geared graph G can be obtained by extending the linear inequalities defining STAB (H) and STAB (H-e), where He is the graph obtained from H by subdividing the edge e. We also introduce the class of G-perfect graphs, i.e., graphs whose stable set polytope is described by nonnegativity inequalities, rank inequalities, lifted 5-wheel inequalities, and some special inequalities called geared inequalities and g-lifted inequalities. We prove that graphs obtained by repeated applications of the gear composition to a given graph H are G-perfect, provided that any graph obtained from H by subdividing a subset of its simplicial edges is G-perfect. In particular, we show that a large subclass of claw-free graphs is G-perfect.