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 chi C\e - chi 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). (c) 2020 Elsevier B.V. All rights reserved.
The Schrijver system of the flow cone in series-parallel graphs
Wolfler Calvo, R
2022-01-01
Abstract
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 chi C\e - chi 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). (c) 2020 Elsevier B.V. All rights reserved.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
