Date of Award
2017
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Mathematical Sciences
Committee Chair
Grant Zhang
Committee Member
Daniel Rochowiak
Committee Member
Dongsheng Wu
Committee Member
Alan Sprague
Committee Member
Brendan Ames
Subject(s)
Domination (Graph theory)
Abstract
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.
Recommended Citation
Sewell, J. Louis, "Vertex-based distinguishing collections" (2017). Dissertations. 134.
https://louis.uah.edu/uah-dissertations/134