×

A polyhedral intersection theorem for capacitated spanning trees. (English) Zbl 0763.90082

Summary: In a two-capacitated spanning tree of a complete graph with a distinguished root vertex \(v\), every component of the induced subgraph on \(V\backslash\{v\}\) has at most two vertices. We give a complete, nonredundant characterization of the polytope defined by the convex hull of the incidence vectors of two-capacitated spanning trees. This polytope is the intersection of the spanning tree polytope on the given graph and the matching polytope on the subgraph induced by removing the root node and its incident edges. This result is one of very few known cases in which the intersection of two integer polyhedra yields another integer polyhedron. We also give a complete polyhedral characterization of a related polytope, the 2-capacitated forest polytope.

MSC:

90C35 Programming involving graphs or networks
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
05C38 Paths and cycles