Z₃-connectivity And Nowhere-zero Flows In Graphs

Tutte introduced the theory of nowhere-zero flows as a tool to attack the 4-color-conjecture. Let D be an orientation of a graph G, and let ED+(v)(ED+(v)) denote the edges with tail (head) at v. If there is a map f:E(G)→{±1,±2....±(k-1)} such that for every vertex v∈V(G), then G admits a nowhere-zero k-flow. Moreover, Tutte conjectured that every 4-cdge-connected graph admits a nowhere-zero 3-flow. In 1992. Jaeger et al. [10] ex-tended nowhere-zero flows to group connectivity of graphs. Let A denote an abclian group with the identity element 0. If for any b:V(G)→A with∑v∈V(G)^ b(v)=0, there is a function f:E(G)→A-{0} such that for each vertex v∈(G), then G is,A-connected. In [10], Jaeger et al. conjectured that every 5-edgc-connected graph is Z3-connected. On these two conjectures, this dissertation does some work as follows.Firstly, we investigate simple bipartite graphs with the minimum degree satis-fying some condition. Let G be a simple bipartite graph on n vertices. It is proved in this paper that ifδ(G)≥[n/4]+1, then G admits a nowhere-zero 3-flow if and only if G is not the exceptional graph. Moreover, if n≥13, G with the minimum degree at least [n/4]+1 is Z3-connected. The bound is best possible in the sense that the lower bound for the minimum degree cannot be decreased.Secondly, we investigate 2-edge-connected simple graphs with neighborhood unions of two nonadjacent vertices satisfying some condition. Let G be a 2-cdge-connected simple graph on n≥14 vertices. If a graph G* is obtained by repeatedly contracting nontrivial Z3-connected subgraphs of G until no such a subgraph left, wc say G can be Z3-reduced to G*. In this paper, we prove that if for every uv (?) E(G), |N(u)∪N(u)|≥[2n/3], then G is not Z3-connected if and only if G can be Z3-reduced to one of {C3,K4. K4-. L}, where L is obtained from K4 by adding a new vertex which is joined to two vertices of K4. Thirdly, we investigate Cayley graphs on generalized dihedral groups and gener-alized quaternion groups, and show that 3-flow conjecture is true for Cayley graphs on these two classes of groups. This generalizes the result in [Information Processing Letters,111 (2011) 416-419] by Yang and Li.Finally, we investigate vertex-transitive graphs on abelian groups, and proved that every vertex-transitive graph of degree at least 4 on abelian groups admits a nowhere-zero 3-flow. This generalized the result in [Discrete Mathematics.297 (2005).119-127] by Potocnik, Skoviera and Skrekovski.