Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647843 | Discrete Mathematics | 2012 | 10 Pages |
Let GG be a 2-edge-connected undirected graph, AA be an (additive) Abelian group, and A∗=A−{0}A∗=A−{0}. A graph GG is AA-connected if GG has an orientation D(G)D(G) such that for every mapping b:V(G)↦A satisfying ∑v∈V(G)b(v)=0∑v∈V(G)b(v)=0, there is a function f:E(G)↦A∗ such that for each vertex v∈V(G)v∈V(G), the sum of ff over the edges directed out from vv minus the sum of ff over the edges directed into vv equals b(v)b(v). For a 2-edge-connected graph GG, define Λg(G)=min{k:Λg(G)=min{k: for any Abelian group AA with |A|≥k|A|≥k, GG is AA-connected }}. Let PP denote a path in GG, let βG(P)βG(P) be the minimum length of a circuit containing PP, and let βi(G)βi(G) be the maximum of βG(P)βG(P) over paths of length ii in GG. We show that Λg(G)≤βi(G)+1Λg(G)≤βi(G)+1 for any integer i>0i>0 and for any 2-connected graph GG. 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. In this paper, we completely determine all graphs GG with Λg(G)=β2(G)+1Λg(G)=β2(G)+1.