Jiaao Li

Date of Graduation

2018

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Hong-Jian Lai

Committee Co-Chair

John Goldwasser

Committee Member

Guodong Guo

Committee Member

Kevin Milans

Committee Member

Cun-Quan Zhang

Abstract

This dissertation focuses on the subject of nowhere-zero flow problems on graphs. Tutte's 5-Flow Conjecture (1954) states that every bridgeless graph admits a nowhere-zero 5-flow, and Tutte's 3-Flow Conjecture (1972) states that every 4-edge-connected graph admits a nowhere-zero 3-flow. Jaeger et al. (1992) further conjectured that every 5-edge-connected graph is Z3-connected, whose truth implies the 3-Flow Conjecture. Extending Tutte's flows conjectures, Jaeger's Circular Flow Conjecture (1981) says every 4p-edge-connected graph admits a modulo (2 p + 1)-orientation, that is, an orientation such that the indegree is congruent to outdegree modulo p + 1 at every vertex. Note that the p = 1 case of Circular Flow Conjecture coincides with the 3-Flow Conjecture, and the case of p = 2 implies the 5-Flow Conjecture. This work is devoted to provide some partial results on these problems.;It is proved in Chapter 2 that every graph with four edge-disjoint spanning trees is Z3-connected. Consequently, Jaeger et al.'s group connectivity conjecture and Tutte's 3-Flow Conjecture hold for 5-edge-connected essentially 23-edge-connected graphs. We also provide several equivalent versions of Jaeger et al.'s group connectivity conjecture and indicate that it is enough to verify the conjecture for 5-edge-connected essentially 8-edge-connected graphs. In Chapter 3, Tutte's 3-Flow Conjecture is verified for graphs with independence number at most 4 .;The relation of orientation and group connectivity is studied in Chapter 4. It shows that every strongly Zm-connected graph contains m-1 edge-disjoint spanning trees, and hence every Z m-connected graph G has (m -- 1)(| V(G)| -- 1)/(m -- 2) edges, which solves a conjecture of Luo et al. (2012). Those results are applied to establish some monotonicity properties of group connectivity that every strongly Z5-connected graph is Z 3-connected, and every Z3-connected graph is A-connected for any Abelian group A with size |A| ≥ 4 .;Infinite families of counterexamples to Jaeger's Circular Flow Conjecture are presented in Chapter 5. For p ≥ 3 , there are 4 p-edge-connected graphs not admitting modulo (p + 1)-orientation; for p ≥ 5 , there are (4p + 1)-edge-connected graphs not admitting modulo (p + 1)-orientation. Towards the p = 2 case of Circular Flow Conjecture and the 5-Flow Conjecture, we show in Chapter 6 that every 10-edge-connected planar graph admits a modulo 5-orientation.

Download

Share

COinS