The k -Edge-Connected Spanning Subgraph Polyhedron

Source abstract

This paper studies the polyhedron $P_k ( G )$ definedd 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 \in \{ 4r - 2, 4r - 1, 4r + 1,r \in t\{ 1,2, \ldots \} \}$ is described.