On Group Connectivity of Graphs

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero Z ₃-flow and Jaeger et al. [Group connectivity of graphs–a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B 56 (1992) 165-182] further conjectured that every 5-edge-connected graph is Z ₃-connected. These two conjectures are in general open and few results are known so far. A weaker version of Tutte’s conjecture states that every 4-edge-connected graph with each edge contained in a circuit of length at most 3 admits a nowhere-zero Z ₃-flow. Devos proposed a stronger version problem by asking if every such graph is Z ₃-connected. In this paper, we first answer this later question in negative and get an infinite family of such graphs which are not Z ₃-connected. Moreover, motivated by these graphs, we prove that every 6-edge-connected graph whose edge set is an edge disjoint union of circuits of length at most 3 is Z ₃-connected. It is a partial result to Jaeger’s Z ₃-connectivity conjecture. Received: May 23, 2006. Final version received: January 13, 2008