Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656995 | Journal of Combinatorial Theory, Series B | 2011 | 16 Pages |
Abstract
The circular flow number Φc(G,σ) of a signed graph (G,σ) is the minimum r for which an orientation of (G,σ) admits a circular r-flow. We prove that the circular flow number of a signed graph (G,σ) is equal to the minimum imbalance ratio of an orientation of (G,σ). We then use this result to prove that if G is 4-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) (as well as Φ(G,σ)) is at most 4. If G is 6-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) is strictly less than 4.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics