Article ID Journal Published Year Pages File Type
4647650 Discrete Mathematics 2013 11 Pages PDF
Abstract

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 G′G′ such that for every map b:V(G)↦Ab:V(G)↦A satisfying ∑v∈V(G)b(v)=0∑v∈V(G)b(v)=0, there is a function f:E(G)↦A∗f:E(G)↦A∗ such that for each vertex v∈V(G)v∈V(G), the total amount of ff-values on the edges directed out from vv minus the total amount of ff-values on the edges directed into vv equals b(v)b(v). Jaeger et al. [F. Jaeger, N. Linial, C. Payan, M. Tarsi, Group connectivity of graphs—a nonhomogeneous analogue of nowhere-zero flow properties, J. Combinatorial Theory, Series B 56 (1992) 165–182] conjectured that every 5-edge-connected graph GG is Z3Z3-connected, where Z3Z3 is the cyclic group of order 3. In this paper we prove that every connected Cayley graph GG of degree at least 5 on an Abelian group is Z3Z3-connected.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , ,