کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656818 1632985 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Group flow, complex flow, unit vector flow, and the (2+ϵ)(2+ϵ)-flow conjecture
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Group flow, complex flow, unit vector flow, and the (2+ϵ)(2+ϵ)-flow conjecture
چکیده انگلیسی

If F is a (possibly infinite) subset of an abelian group Γ  , then we define f(F,Γ)f(F,Γ) as the smallest natural number such that every f(F,Γ)f(F,Γ)-edge-connected (finite) graph G has a flow where all flow values are elements in F  . We prove that f(F,Γ)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⩾3k⩾3, every (3k−1)(3k−1)-edge-connected graph has a collection of k   even subgraphs such that every edge is in precisely k−1k−1 of them. Finally, the flow result gives a considerable freedom to prescribe the flow values in the (2+ϵ)(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/k1+1/k. It also has, for any irrational number ϵ  , a flow with flow values 1, 1+ϵ1+ϵ, 1+ϵ+1/k1+ϵ+1/k.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 108, September 2014, Pages 81–91
نویسندگان
,