Group Connectivity And Nowhere-zero Integer Flows Of Graphs

Graph theory has a close relationship with famous4-color problem. It is also called4-color-conjecture:it was indeed possible to colour any map in four colours such that the states of common boundary have different colours. Tutte introduced the theory of nowhere-zero flows as a tool to attack the4-color-problem, together with his most fascinating conjectures on nowhere-zero flows. Tutte conjectures that there exists a integer k such that every bridgeless graph admits a nowhere zero k-flow. Now, this conjecture is still open. It is known that Petersen graph which is bridgeless admits no nowhere zero4-flow, then5is the best possibility. It is the famous5-flow conjecture when k=5. Tutte conjectures that every bridgeless graph containing no subdivision of the Petersen graph admits a nowhere zero4-flow, and Tutte further conjectures that every4-edge-connected graph admits a nowhere zero3-flow. The above are the famous3-flow,4-flow and5-flow conjectures.In1992,Jaeger et al. successfully generalized nowhere-zero flow problems to group connectivity. Group connectivity is not only the generalization of nowhere-zero flow, but also favorable property:Let A be Abelian group with|A|=k, and let H be a subgraph of G. If H is A-connected and G/H admits nowhere zero k-flow, then G admits nowhere zero k-flow. For group connectivity, Jaeger et al. posed two famous conjectures:Za-and Z5-connectivity conjectures which are that every3-edge-connected graph is Z5-connected and that every5-edge-connected graph is Z3-connected. On these conjectures, this dissertation does some work as follows.Firstly, we investigate3-edge-connected simple graphs with the small vertex. Let G be a3-edge-connected graph on n vertices and A an abelian group with|A|>5. If n≤15or n=16and Δ>4or n=17and Δ≥5, then G is A-connected. For applications, we obtain the following two results. Let G be a3-edge-connected simple graph on n vertices and A an abelian group with|A|≥5. If|E(G)|≥(n-15/2)+31where n≥17, then G is A-connected. If a graph G*is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say G can be A-reduced to G*. Let G be a3-edge-connected simple graph on n vertices and A an abelian group with|A|≥4. If|E(G)|≥(n-11/2)+23where n≥13, then either G is A-connected or G can be A-reduced to the Petersen graph.Secondly, we investigate the relationship between the group connectivity and independent edges number in3-edge-connected simple graphs.Let A be an abelian group with|.|A|>4. If G is a3-edge-connected simple graph and α’(G)≤5, then either G is A-connected or G can be A-reduced to the Petersen graph. Further shows that if G satisfies above conditions and|A|≥5, then G is A-connected.Finally, we investigate group connectivity of locally connected groups. Let G be3-edge-connected simple graph with H, K1，3-free. If G is locally connected, then G is not Z3-connected if only and if G is one of the two graphs in Fig4-1. if...