Degree Name
MS (Master of Science)
Program
Mathematical Sciences
Date of Award
5-2007
Committee Chair or Co-Chairs
Teresa W. Haynes
Committee Members
Robert B. Gardner, Yared Nigussie
Abstract
For a graph G=(V,E), a nonempty subset S contained in V is called a defensive alliance if for each v in S, there are at least as many vertices from the closed neighborhood of v in S as in V-S. If there are strictly more vertices from the closed neighborhood of v in S as in V-S, then S is a strong defensive alliance. A (strong) defensive alliance is called global if it is also a dominating set of G. The alliance partition number (respectively, strong alliance partition number) is the maximum cardinality of a partition of V into defensive alliances (respectively, strong defensive alliances). The global (strong) alliance partition number is defined similarly. For each parameter we give both general bounds and exact values. Our major results include exact values for the alliance partition number of grid graphs and for the global alliance partition number of caterpillars.
Document Type
Thesis - unrestricted
Recommended Citation
Lachniet, Jason, "Alliance Partitions in Graphs." (2007). Electronic Theses and Dissertations. Paper 2080. https://dc.etsu.edu/etd/2080
Copyright
Copyright by the authors.