Tree reconstruction, directed cycles and flow decompositions /by Manuel J. Welhan.

This dissertation consists of three chapters, each concerning a separate topic within the field of graph theory. (1) The vertex-reconstruction problem has motivated graph theorists for seventy years. Harary and Lauri have conjectured that every tree is class-reconstructible from some two vertex-deleted subgraphs. By using properties of isomorphisms of trees, and an approach similar to Kocay's treatment of isomorphisms in the general vertex-reconstruction problem, we give a proof that this conjecture holds for homeomorphically irreducible trees. (2) Many fundamental problems concerning cycles in digraphs remain open. Of particular interest are those extremal problems that involve minimum degree conditions, since they tend to be intractable when usual methods for undirected graphs are applied. The Ho{grave}ang-Reed Conjecture states that a digraph with minimum out-degree d contains d directed circuits that have a forest-like structure. By using Menger's Theorem in a new way, we give a proof of the d =3 case of the Ho{grave}ang-Reed Conjecture. (3) The theorems for 4-flows, 6-flows and 8-flows due to Tutte, Seymour and Jaeger, respectively, all rely on covering a graph with smaller 2- or 3-flows. Zhang and Xie have recently made conjectures that might make 5-flows vulnerable to this sort of approach as well. A relationship between face-colorings and sums of 2-flows allows us to give new characterizations of graphs admitting orientable 5-cycle double covers. We also show that every Z{esc}b4{esc}s-flow arises from a face-Z{esc}b4{esc}s-coloring of an embedding in an orientable surface.Thesis (Ph. D., Mathematics)--University of Idaho, May 2010