Originators: Francois Jaeger et. al., Riu Xu (presented by Jane Butterfield - REGS 2010)
Definitions: These concepts and the basic results about them are due to Jaeger, Linial, Payan, & Tarsi [JLPT]. Let G be a graph, let G' be an orientation of G, and let A be an additive abelian group (identity element 0). For x∈V(G), let E -(x) and E +(x) be the sets of edges entering and leaving in G', respectively. The boundary of a function f: E(G) → A is the function ∂f: V(G) → A given by ∂f(x) = ΣE +(x) f(e) - ΣE -(x) f(e). Let F(G,A) denote the set of all functions from E(G) to A; these are the A-labelings of G. The A-labeling that do not assign the identity element 0 to any edge are the nowhere-zero A-labelings.
An A-flow on G is an A-labeling whose boundary (relative to a fixed reference orientation G') is 0 at every vertex. Let F0(G,A) denote the set of A-flows on G. A nowhere-zero A-flow on G, abbreviated A-NZF, is a nowhere-zero A-labeling that is also an A-flow.
[JLPT] noted that a result of Tutte [T] implies that the existence of an A-NZF on a graph G depends only on the order of A. Thus, "G admits [or has] a k-NZF" means that for every Abelian group of order k> there is an A-NZF on G. When A is Zk, the cyclic group of order k, an A-NZF is called a nowhere-zero k-flow or k-NZF; we say that G is k-flowable when this exists. [Editorial note: The minimum k such that G is k-flowable is the flow number of G, and the term "k-flowable" is motivated by the natural duality between nowhere-zero k-flows and proper k-colorings.]
A zero-sum function is a function b: V(G) → A such that Σv∈V(G)b(v) = 0. A graph G is A-connected if for every orientation G' of G, every zero-sum function is the boundary of some nowhere-zero function on G. In fact, it suffices to consider any one orientation, since reversing an edge and negating the value of f on it yields does not change the contribution to the boundary at the endpoints. Hence we simply assume a fixed reference orientation, such as orienting all edges toward the higher-indexed endpoint.
Background: Group connectedness is closely related to connectedness, since an easy inductive proof [JLPT] shows that G is connected if and only if every zero-sum function b: V(G) → A is the boundary of some A-labeling. [Editorial note: In the literature, the term "group connectivity" is often used for "group connectedness", because [JLPT] used "A-connectivity" to mean "the property of being "A-connected", but "A-connected" gives no numerical measure of connectivity. There is a sensible related definition of group connectivity; it is the minimum k such that G is A-connected for every abelian group A of order at least k (see [HY]). Somewhat paradoxically, a graph thus has smaller group connectivity when it is "more highly connected".]
The notion of A-connectedness generalizes that of nowhere-zero k-flows. The conjectures posed later generalize these well-known flow conjectures of Tutte:
Conjecture 1 (Tutte): Every 2-edge-connected graph is 5-flowable.
Conjecture 2 (Tutte): Every 2-edge-connected graph not having the
Petersen graph as a minor is 4-flowable.
Conjecture 3 (Tutte): Every 4-edge-connected graph is 3-flowable.
Comments: Seymour [S] proved that every 2-edge-connected graph is 6-flowable, and [AGZ] is related to Conjecture 2 and to the Cycle Double Cover Conjecture). There are other partial results toward these conjectures (see the book [Z]). Jaeger [J] proved the weaker version of Conjecture 3 that every 4-edge-connected graph is 4-flowable. Kochol [K] showed that to prove Conjecture 3 it suffices to prove it for 5-edge-connected graphs.
A weaker version of Conjecture 3 is that 4-edge-connected graphs in which every edge lies in a cycle of length at most 3 are 3-flowable. Adding a structural condition suffices: A graph is triangularly connected if for every two edges e and e' not having the same endpoints, there is a list of triangles such that e is in the first, e' is in the last, consecutive triangles have exactly one common edge, and nonconsecutive triangles are edge-disjoint. Fan, Lai, Xu, Zhang, & Zhou [FLXZZ] completely determined the triangularly connected graphs that are not 3-flowable. As a consequence, Conjecture 3 holds for triangularly connected graphs.
Group connectedness is stronger than the existence of nowhere-zero flows. For example, 2-flowability is equivalent to being Eulerian, but K1 is the only Z2-connected graph. Similarly, although Conjecture 3 remains open, [JLPT] presents a 4-regular, 4-edge-connected graph that is not Z3-connected (starting with the 3-regular graph 3K4, add a perfect matching that joins two vertices of each 4-clique to two vertices in the next 4-clique, cyclically). DeVos asked whether 4-edge-connected graphs in which every edge lies in a cycle of length at most 3 are Z3-connected. The answer is no, with an infinite family of counterexamples in [LXZ]. This brings us to analogous conjectures about group connectedness.
Conjecture 4 ([JLPT]):
Every 3-edge-connected graph is Z5-connected.
Conjecture 5 ([JLPT]):
Every 5-edge-connected graph is Z3-connected.
Conjecture 6 ([JLPT]):
For some integer j, every j-edge-connected graph is
Z3-connected.
Comments: Conjecture 4 would imply Conjecture 1, because the smallest counterexample to Conjecture 1 must be 3-edge-connected. Relating Conjectures 3 and 6, [JLPT] proved that if every k-edge-connected graph is 3-flowable, then every (2k+2)-edge-connected graph is Z3-connected. Thus Conjecture 6 is equivalent to the weak form of Conjecture 3 that asserts the existence of such a value k, and Conjecture 3 implies that every 10-edge-connected graph is Z3-connected.
Lai, Xu, & Zhou [LXZ] proved a statement that is weaker than both Conjecture 5 and Conjecture 6: If G is 6-edge-connected and decomposes into cycles of length at most 3, then G is Z3-connected. Since Z3-connectedness is well-studied, and there are many partial results about it, problems about Z5-connectedness may be more accessible.
Nowhere-zero flows satisfy a monotonicity condition like k-colorability: all k-flowable graphs are (k+1)-flowable, because a k-NZF on G is also a (k+1)-NZF. On the other hand, [JLPT] showed that A-connectedness is not monotone. For example, the graph consisting of four internally-disjoint 4-vertex paths with common endpoints is Z5-connected but not Z6-connected.
In [JLPT], several equivalent conditions were obtained for A-connectedness. They showed that a graph is A-connected if and only if for every A-labeling f of G, there is an A-flow f ' that differs from f on every edge. Another equivalent condition is that for every A-labeling f of G and every zero-sum function b on V(G), there is an A-labeling with boundary b that differs from f on every edge.
As mentioned earlier, the existence of an A-NZF in G depends only on |A|. It is unknown whether the corresponding statement for A-connectedness is true, even for the smallest nontrivial value.
Question 7 ([JLPT]): Is the family of Z4-connected graphs the same as the family of Z2×Z2-connected graphs?
Comments: [JLPT] modified the proof by Jaeger [J] that 4-edge-connected graphs are 4-flowable to show that if |A|≥4 and G has two edge-disjoint spanning trees, then G is A-connected. Thus differences between the two families in Question 7 must come from graphs that are not 4-edge-connected.
Sufficient denseness makes any graph A-connected. Ore's Condition is the statement that the degrees of any two nonadjacent vertices sum to at least the number of vertices in the graph. Luo, Xu, Yin, & Yu [LXYY] proved that if G is a simple graph with at least three vertices that satisfies Ore's Condition, then G is A-connected for every abelian group A with order at least 3, except for 12 particular graphs. One may also consider average degree:
Conjecture 8 (Xu [X]):
With dave(A,n) denoting the smallest average degree among the
A-connected n-vertex graphs,
1) dave(Z3,n) ≥ 4 - 4/n, and
2) dave(A,n) ≥ 3 - 3/n whenever |A|≥4.
Comments: It is known that dave(Z3,n) ≥ 3 and that in general dave(A,n)≥ 8/3 - 2/(3n) when |A|≥4. See also an earlier REGS page.
References:
[AGZ] B. Alspach, L. A. Goddyn and C.-Q. Zhang, Graphs with the circuit cover
property, Trans Amer Math Soc 344(1) (1994), 131--154.
[DXY] M. DeVos, R. Xu, G. Yu, Nowhere-zero Z3-flows
through Z3-connectivity. Discrete Mathematics 306, 26-30
(2006).
[FLXZZ] G. Fan, H. Lai, R. Xu, C. Zhang, C. Zhou, Nowhere-zero 3-flows in
triangularly-connected graphs. Journal of Combinatorial Theory, Series B
98, 1325-1336 (2008).
[J] F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin.
Theory Ser. B 26 (1979), 205-216.
[JLPT] F. Jaeger, N. Linial, C. Payan, M. Tarsi, Group connectivity
of graphs -- a nonhomogeneous analogue of nowhere-zero flow properties.
Journal of
Combinatorial Theory, Series B 56, 165-182 (1992).
[K] Kochol, Martin; An equivalent version of the 3-flow conjecture.
J. Combin. Theory Ser. B 83 (2001), no. 2, 258--261.
[LXYY] R. Luo, R. Xu, J. Yin, G. Yu, Ore-condition and
Z3-connectivity. European Journal of Combinatorics
[LXZ] H. Lai, R. Xu, J. Zhou, On Group Connectivity of Graphs. Graphs and
Combinatorics 24, 195-203 (2008).
[LY] Lai, Hong-Jian; Yao, Xiangjuan Group connectivity of graphs with diameter
at most 2. European J. Combin. 27 (2006), no. 3, 436--443.
[S] Seymour, P. D. Nowhere-zero 6-flows. J. Combin. Theory Ser. B 30
(1981), no. 2, 130--135.
[T] W.T. Tutte, A contribution to the theory of chromatic polynomials,
Canad. J. Math. 6 (1954), 80-91.
[X] R. Xu, Degree sum and Z3-connectivity,
submitted.
[Z] Zhang, Cun-Quan; Integer flows and cycle covers of graphs. Monographs and
Textbooks in Pure and Applied Mathematics, 205. Marcel Dekker, Inc., New York,
1997. xii+379 pp.