Date of Award


Document Type


Degree Name

Doctor of Philosophy (PhD)


Mathematical Sciences

Committee Chair

Grant Zhang

Committee Member

Daniel Rochowiak

Committee Member

Dongsheng Wu

Committee Member

Alan Sprague

Committee Member

Brendan Ames


Domination (Graph theory)


This work introduces vertex-based distinguishing collections that generalize locating-dominating sets and other well-studied sets related to sensor placement in a graph. A graph is an ordered pair G = (V, E), where V is an arbitrary set and E is a set of unordered pairs of elements of V. Graphical sensor placement problems are concerned with selecting or recognizing a subset of vertices X ⊆ V such that X has certain sensing or location-distinguishing properties. For example, a locating-dominating set of G is a set of vertices X ⊆ V such that: every vertex not in X shares an edge with at least one vertex in X; and for every distinct pair of vertices in V \ X, there is a vertex in X that shares an edge with one vertex in the pair but not the other. Mathematical tools are developed in the language of binary integer programs to compare minimum sizes of closely related vertex-based distinguishing~collections.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.