The graceful tree conjecture was first introduced over 50 years ago, and to this day it remains largely unresolved. Ideas for how to label arbitrary trees have been sparse, and so most work in this area focuses on demonstrating that particular classes of trees are graceful. In my research, I continue this effort and establish the gracefulness of some new tree types using previously developed techniques for constructing graceful trees. Meanwhile, little work has been done on developing computational methods for obtaining graceful labelings, as direct approaches are computationally infeasible for even moderately large trees. With this in mind, I have designed a new computational approach for constructing a graceful labeling for trees with sufficiently many leaves. This approach leverages information about the local structures present in a given tree in order to construct a suitable labeling. It has been shown to work for many small cases and thoughts on how to extend this approach for larger trees are put forth. / McAnulty College and Graduate School of Liberal Arts; / Computational Mathematics / MS; / Thesis;

A decomposition D of a graph H by a graph G is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. A mixed graph on V vertices is an ordered pair (V,C), where V is a set of vertices, |V| = v, and C is a set of ordered and unordered pairs, denoted (x, y) and [x, y] respectively, of elements of V [8]. An ordered pair (x, y) ∈ C is called an arc of (V,C) and an unordered pair [x, y] ∈ C is called an edge of graph (V,C). A path on n vertices is denoted as Pn. A partial orientation on G is obtained by replacing each edge [x, y] ∈ E(G) with either (x, y), (y, x), or [x, y] in such a way that there are twice as many arcs as edges. The complete mixed graph on v vertices, denoted Mv, is the mixed graph (V,C) where for every pair of distinct vertices v1, v2 ∈ V , we have {(v1, v2), (v2, v1), [v1, v2]} ⊂ C. The goal of this thesis is to establish necessary and sufficient conditions for decomposition of Mv by all possible partial orientations of P4.