Physical Sciences and Mathematics Commons^™

Weighted Modulo Orientations Of Graphs, Jianbing Liu

Graduate Theses, Dissertations, and Problem Reports

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. Extending Tutte's flows conjectures, Jaeger's Circular Flow Conjecture (1981) says every 4k-edge-connected graph admits a modulo (2k+1)-orientation, that is, an orientation such that the indegree is congruent to outdegree modulo (2k+1) at every vertex. Note that the k=1 case of Circular Flow Conjecture coincides with the 3-Flow Conjecture, and the case of k=2 implies the 5-Flow Conjecture. This work is devoted …