Circular flow on signed graphs |
| |
Authors: | Andre Raspaud Xuding Zhu |
| |
Affiliation: | aLaBRI, Universite Bordeaux I, France;bDepartment of Mathematics, Zhejiang Normal University, Jinhua, China |
| |
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. |
| |
Keywords: | Signed graph Circular flow number Bidirected graph |
本文献已被 ScienceDirect 等数据库收录! |
|