GROUP CONNECTIVITY, STRONGLY Zm-CONNECTIVITY, AND EDGE DISJOINT SPANNING TREES

Let Z(m) be the cyclic group of order m >= 3. A graph G is Z(m)-connected if G has an orientation D such that for any mapping b : V(G) -> Z(m) with Sigma v is an element of V(G) has an orientation D such that for any mapping integral : E(G) -> Z(m) - {0} satisfying Sigma(+)(e is an element of ED) (v) integral(e) - Sigma(-)(e is an element of ED) integral(G) b(e) = b(v) = 0, there exists a mapping for any v is an element of V(G); and a graph G is strongly Z(m)-connected if, for any mapping theta : V(G) -> Zm with E,,v(G) 9(v) = vertical bar E(G)vertical bar in there is an orientation D such that d(D)(+)(v) = 9(v) in 7L for each v is an element of V(G). In this paper, we study the relation between Z(m)-connected graphs and strongly Z(m)-connected graphs and show that a graph G is Zm-connected if and only if (m - 2)G is strongly Z(m)-connected, where (m - 2)G is the graph obtained from G by replacing each edge in G with m - 2 parallel edges. We also show that if G is Z(m)-connected, then (m(2))G has m 1 edge disjoint spanning trees. Those results together with a result by Jaeger et al. [T. Cominn. Theory Ser. B, 56 (1992), pp. 165-182] imply that every Z(m)-connected graph is A-connected for any abelian group A with vertical bar A vertical bar > 4. They are applied to determine the exact values of ex(n, Z,,) for all m >= 3, where ex(n,Z(m)) is the largest integer such that every simple graph on n vertices with at most ex(n,Z,,) edges is not Z(m)-connected, and to present characterizations of graphic and multigraphic sequences that have Z(m)-connected realizations.