首页|The Schrijver system of the flow cone in series–parallel graphs
The Schrijver system of the flow cone in series–parallel graphs
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
? 2020 Elsevier B.V.We represent a flow of a graph G=(V,E) as a couple (C,e) with C a circuit of G and e an edge of C, and its incidence vector is the 0/±1 vector χC?e?χe. The flow cone of G is the cone generated by the flows of G and the unit vectors. When G has no K5-minor, this cone can be described by the system x(M)≥0 for all multicuts M of G. We prove that this system is box-totally dual integral if and only if G is series–parallel. Then, we refine this result to provide the Schrijver system describing the flow cone in series–parallel graphs. This answers a question raised by Chervet et al., (2018).
NSTL
Elsevier
