THE ST-BOND POLYTOPE ON SERIES-PARALLEL GRAPHS

摘要

The st-bond polytope of a graph is the convex hull of the incidence vectors of its st-bonds, where an st-bond is a minimal st-cut. In this paper, we provide a linear description of the st-bond polytope on series-parallel graphs. We also show that the st-bond polytope is the intersection of the st-cut dominant and the bond polytope.