THE K-EDGE-CONNECTED SPANNING SUBGRAPH POLYHEDRON

This paper studies the polyhedron P(k)(G) defined by the convex hull of k-edge-connected spanning subgraphs of a given graph G where multiple copies of an edge are allowed. A complete inequality description of P(k)(G) when k is odd and G is an outer planar graph is given. A family of facet-defining inequalities of P(k)(G) that have the same support graph but coefficients that depend on k is-an-element-of {4r - 2, 4r - 1, 4r + 1, r is-an-element-of {1, 2....}} is described.