On two-connected subgraph polytopes

✍ Scribed by Francisco Barahona; Ali Ridha Mahjoub

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 674 KB
• Volume: 147
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00255-h

✦ Synopsis

We further study some known families of valid inequalities for the 2-edge-connected and 2-node-connected subgraph polytopes. For the 2-edge-connected case, we show that the odd wheel inequalities together with the obvious constraints give a complete description of the polytope for Halin graphs. For 2-node-connected subgraphs, we show that the inequalities above, plus the partition inequalities, describe the polytope for the same class of graphs.