Semester

Summer

Date of Graduation

2012

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Hong-Jian Lai.

Abstract

Tutte introduced the theory of nowhere-zero flows and showed that a plane graph G has a face k-coloring if and only if G has a nowhere-zero A-flow, for any Abelian group A with |A| ≥ k. In 1992 Jaeger et al. [16] extended nowhere-zero flows to group connectivity of graphs: given an orientation D of a graph G, if for any b: V (G) A with sumv∈ V(G ) b(v) = 0, there always exists a map ƒ: E(G) A - {lcub}0{rcub}, such that at each v ∈ V(G), e=vw isdirectedfrom vtow fe- e=uvi sdirectedfrom utov fe=b v in A, then G is A-connected. For a 2-edge-connected graph G, define Lambda g(G) = min{lcub}k: for any Abelian group A with |A| ≥ k, G is A-connected{rcub}.;Let G1 ⊗ G2 and G1 xG2 denote the strong and Cartesian product of two connected nontrivial graphs G1 and G2. We prove that Lambdag(G 1 ⊗ G2) ≤ 4, where equality holds if and only if both G1 and G 2 are trees and min{lcub}|V (G1)|, |V (G2)|{rcub}=2; Lambda g(G1 ⊗ G 2) ≤ 5, where equality holds if and only if both G 1 and G2 are trees and either G 1 ≅ K1, m and G2 ≅ K 1,n, for n, m ≥ 2 or min{lcub}|V (G1)|, | V (G2)|{rcub}=2. A similar result for the lexicographical product graphs is also obtained.;Let P denote a path in G, let beta G(P) be the minimum length of a circuit containing P, and let betai(G) be the maximum of betaG(P) over paths of length i in G. We show that Lambda g(G) ≤ betai( G) + 1 for any integer i > 0 and for any 2-connected graph G. Partial solutions toward determining the graphs for which equality holds were obtained by Fan et al. in [J. Comb. Theory, Ser. B, 98(6) (2008), 1325-1336], among others. We completely determine all graphs G with Lambda g(G) = beta2(G) + 1.;Let Z3 denote the cyclic group of order 3. In [16], Jaeger et al. conjectured that every 5-edge-connected graph is Z3 -connected. We proved the following: (i) Every 5-edge-connected graph is Z3 -connected if and only if every 5-edge-connected line graph is Z3 -connected. (ii) Every 6-edge-connected triangular line graph is Z3 -connected. (iii) Every 7-edge-connected triangular claw-free graph is Z3 -connected. In particular, every 6-edge-connected triangular line graph and every 7-edge-connected triangular claw-free graph have a nowhere-zero 3-flow.

Download

Share

COinS