^{1} Department of Applied Mathematics and Computer Science, Technical University of Denmark^{2} Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark

DOI:

10.1016/j.jctb.2014.02.012

Abstract:

If F is a (possibly infinite) subset of an abelian group Γ, then we define f(F,Γ) as the smallest natural number such that every f(F,Γ)-edge-connected (finite) graph G has a flow where all flow values are elements in F. We prove that f(F,Γ) exists if and only if some odd sum of elements in F equals some even sum. We discuss various instances of this problem. We prove that every 6-edge-connected graph has a flow whose flow values are the three roots of unity in the complex plane. If the edge-connectivity 6 can be reduced, then it can be reduced to 4, and the 3-flow conjecture follows. We prove that every 14-edge-connected graph has a flow whose flow values are the five roots of unity in the complex plane. Any such flow is balanced modulo 5. So, if the edge-connectivity 14 can be reduced to 9, then the 5-flow conjecture follows, as observed by F. Jaeger. We use vector flow to prove that, for each odd natural number k⩾3, every (3k−1)-edge-connected graph has a collection of k even subgraphs such that every edge is in precisely k−1 of them. Finally, the flow result gives a considerable freedom to prescribe the flow values in the (2+ϵ)-flow conjecture by L. Goddyn and P. Seymour. For example, if k is a natural number and G is a 6k-edge-connected graph, then G has a flow with flow values 1, 1+1/k. It also has, for any irrational number ϵ, a flow with flow values 1, 1+ϵ, 1+ϵ+1/k.

Type:

Journal article

Language:

English

Published in:

Journal of Combinatorial Theory. Series B, 2014, Vol 108, p. 81-91

Keywords:

Group flow; Unit vector flow; Orientations modulo k; (2+ϵ)-flow conjecture