|
|||||
|
|
Zero-Sum Flows in Regular Graphs |
|
| Authors: | S. Akbari A. Daemi O. Hatami A. Javanmard A. Mehrabian |
| Affiliation: | 1. Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran 5. School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran 2. Department of Mathematics, Harvard University, Cambridge, USA 3. Department of Electrical Engineering, Stanford University, Stanford, USA 4. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada |
| Abstract: | For an undirected graph G, a zero-sum flow is an assignment of non-zero real numbers to the edges, such that the sum of the values of all edges incident with each vertex is zero. It has been conjectured that if a graph G has a zero-sum flow, then it has a zero-sum 6-flow. We prove this conjecture and Bouchet’s Conjecture for bidirected graphs are equivalent. Among other results it is shown that if G is an r-regular graph (r ≥ 3), then G has a zero-sum 7-flow. Furthermore, if r is divisible by 3, then G has a zero-sum 5-flow. We also show a graph of order n with a zero-sum flow has a zero-sum (n + 3)2-flow. Finally, the existence of k-flows for small graphs is investigated. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |