Semester

Summer

Date of Graduation

2007

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Cun-Quan Zhang.

Abstract

Tutte [45] conjectured that every bridgeless Petersen-minor free graph admits a nowhere-zero 4-flow. Let P10 m&d1; ) be the graph obtained from the Petersen graph by contracting mu edges from a perfect matching. In chapter 1 we prove that every bridgeless P10 3&d1; -minor free graph admits a nowhere-zero 4-flow.;Walton and Welsh [48] proved that if a coloopless regular matroid M does not have a minor in {lcub}M(K 3,3), M*(K5){rcub}, then M admits a nowhere zero 4-flow. Lai et al [27] proved that if M does not have a minor in {lcub}M( K5), M*(K5){rcub}, then M admits a nowhere zero 4-flow. We prove in chapter 2 that if a coloopless regular matroid M does not have a minor in MP10 3&d1;, M*K5 , then M admits a nowhere zero 4-flow. This result implies Walton and Welsh [48] and Lai et al [27].;The odd-edge-connectivity of a graph G, denoted by lambda o(G), is the size of the smallest odd edge-cut of G. In chapter 3, some methods are developed to deal with small even edge-cuts and therefore, extending some earlier results from edge-connectivity to odd-edge-connectivity. One of the main results in chapter 3 solves an open problem that every odd-(2k + 1)-edge-connected graph has k edge-disjoint parity subgraphs. Another main theorem in the chapter generalizes an earlier result by Galluccio and Goddyn (Combinatorica 2002) that the flow index of every odd-7-edge-connected graph is strictly less than 4. It is also proved in this paper if lambda o(G) ≥ 4log2 &vbm0;VG&vbm0; , then G admits a nowhere-zero 3-flow which is a partial result to the weak 3-flow conjecture by Jaeger and improves an earlier result by Lai and Zhang[24].

Download

Share

COinS