solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看123次
Bounded-Excess Flows in Cubic Graphs. (arXiv:1807.04196v1 [math.CO])
来源于:arXiv
An (r,alpha)-bounded excess flow ((r,alpha)-flow) in an orientation of a
graph G=(V,E) is an assignment of a real "flow value" between 1 and r-1 to
every edge. Rather than 0 as in an actual flow, some flow excess, which does
not exceed alpha may accumulate in any vertex. Bounded excess flows suggest a
generalization of Circular nowhere zero flows, which can be regarded as
(r,0)-flows. We define (r,alpha) as Stronger or equivalent to (s,beta) If the
existence of an (r,alpha)-flow in a cubic graph always implies the existence of
an (s,beta)-flow in the same graph. Then we study the structure of the
two-dimensional flow strength poset. A major role is played by the "Trace"
parameter: tr(r,alpha)=(r-2alpha) divided by (1-alpha). Among points with the
same trace the stronger is the one with the larger r (an r-cnzf is of trace r).
About one half of the article is devoted to proving the main result: Every
cubic graph admits a (3.5,0.5)-flow. tr(3.5,0.5)=5 so it can be considered a
step in the 查看全文>>