ETD RECORD
Tree reconstruction, directed cycles and flow decompositions
Citation
Welhan, Manuel J.. (2010). Tree reconstruction, directed cycles and flow decompositions. Theses and Dissertations Collection, University of Idaho Library Digital Collections. https://www.lib.uidaho.edu/digital/etd/items/etd_71.html
- Title:
- Tree reconstruction, directed cycles and flow decompositions
- Author:
- Welhan, Manuel J.
- Date:
- 2010
- Keywords:
- Graph theory Trees (Graph theory) Paths and cycles (Graph theory)
- Program:
- Mathematics
- Abstract:
- 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.
- Description:
- Thesis (Ph. D., Mathematics)--University of Idaho, May 2010.
- Major Professor:
- Hong Wang.
- Defense Date:
- May 2010.
- Type:
- Text
- Format Original:
- xii, 209 leaves :ill. ;29 cm.
- Format:
- record
Rights
- Rights:
- In Copyright - Educational Use Permitted. For more information, please contact University of Idaho Library Special Collections and Archives Department at libspec@uidaho.edu.
- Standardized Rights:
- http://rightsstatements.org/vocab/InC-EDU/1.0/