An Open Locating-Dominating Set (OLD set) is a subset of vertices in a graph such that every vertex in the graph has a neighbor in the OLD set and every vertex has a unique set of neighbors in the OLD set. This can also represent where sensors, capable of detecting an event occurrence at an adjacent vertex, could be placed such that one could always identify the location of an event by the specific vertices that indicated an event occurred in their neighborhood. By the open neighborhood construct, which differentiates OLD sets from identifying codes, a vertex is not able to report if it is the location of the event. This construct provides a robustness over identifying codes and opens new applications such as disease carrier and dark actor identification in networks. This work explores various aspects of OLD sets, beginning with an Integer Linear Program for quickly identifying the optimal OLD set on a graph. As many graphs do not admit OLD sets, or there may be times when the total size of the set is limited by an external factor, a concept called maximum covering OLD sets is developed and explored. The coverage radius of the sensors is then expanded in a presentation of Mixed-Weight OLD sets where sensors can cover more than just adjacent vertices. Finally, an application is presented to optimally monitor criminal and terrorist networks using OLD sets and related concepts to identify the optimal set of surveillance targets.

A set S of vertices in a graph G = (V, E) is a locating-dominating set if S is a dominating set of G, and every pair of distinct vertices {u, v} in V - S is located with respect to S, that is, if the set of neighbors of u that are in S is not equal to the set of neighbors of v that are in S. We give a construction of trees that have unique minimum locating-dominating sets.

Understanding RNA molecules is important to genomics research. Recently researchers at the Courant Institute of Mathematical Sciences used graph theory to model RNA molecules and provided a database of trees representing possible secondary RNA structures. In this thesis we use domination parameters to predict which trees are more likely to exist in nature as RNA structures. This approach appears to have promise in graph theory applications in genomics research.