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.
Recommended Citation
Li, Jiaao, "Group Connectivity and Modulo Orientations of Graphs" (2018). Graduate Theses, Dissertations, and Problem Reports. 7106.
https://researchrepository.wvu.edu/etd/7106
