“Polar Targets”

A dominating target D is a set of vertices in a graph G such that every connected superset of D is a dominating set. An asteroidal set is a set of vertices such that the removal of the neighborhood of one vertex leaves the others connected. In this defense, we introduce the much stronger notion of a polar target, a collection of subsets T1,T2, … ,Tk ? V such that D is a dominating target of size k if and only if |D ? Ti| = 1 for all i. Our main contribution is to prove that if G has a dominating 4-distant asteroidal triple then it has a polar target of size 3. Along the way, we develop strong results about the possible interactions between dominating targets and asteroidal sets.

Committee:
Jamie Radcliffe (Advisor)
Witty Srisa-an (Co-advisor)
Nirnimesh Ghose
Qiuming Yao
Peter Angeletti