科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let G be a 2-edge-connected undirected graph, A be an (additive) Abelian group, and A* = A - (0). A graph G is A-connected if G has an orientation D(G) such that for every mapping b: V(G) bar right arrow A satisfying Sigma(nu is an element of V(G)) b(nu) = 0, there is a function f : E(G) bar right arrow A* such that for each vertex nu is an element of V(G), the sum off over the edges directed out from nu minus the sum off over the edges directed into v equals b(v). For a 2-edge-connected graph G, define Lambda(g)(G) = min{k: for any Abelian group A with vertical bar A vertical bar >= k, G is A-connected }. Let P denote a path in G, let beta(G)(P) be the minimum length of a circuit containing P, and let beta(i)(G) be the maximum of beta(G)(P) over paths of length i in G. We show that Lambda(g)(G) <= beta(i)(G) + 1 for any integer i > 0 and for any 2-connected graph G. Partial solutions toward determining the graphs for which equality holds were obtained by Fan et al. in [G. Fan, H.-J. Lai, R. Xu, C.-Q. Zhang, C. Zhou, Nowhere-zero 3-flows in triangularly connected graphs, Journal of Combinatorial Theory, Series B 98 (6) (2008) 1325-1336], among others.
