"Integer flow and Petersen minor" by Taoye Zhang

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].

Share

COinS