On two connected subgraph polytopes

Mahjoub, Ali Ridha; Barahona, Francisco

Mahjoub, Ali Ridha; Barahona, Francisco (1995), On two connected subgraph polytopes, Discrete Mathematics, 147, 1, p. 19-34. http://dx.doi.org/10.1016/0012-365X(94)00255-H

Type

Article accepté pour publication ou publié

Date

1995

Journal name

Discrete Mathematics

Volume

147

Number

Publisher

Elsevier

Pages

19-34

Abstract (EN)

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.

Subjects / Keywords

Polytope; Inequalities