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.
","abstract_html":"<p>For a graph <em>G</em>=(<em>V</em>,<em>E</em>), a nonempty subset <em>S</em> contained in <em>V</em> is called a <em>defensive alliance</em> if for each <em>v</em> in <em>S</em>, there are at least as many vertices from the closed neighborhood of <em>v</em> in <em>S</em> as in <em>V</em>-<em>S</em>. If there are strictly more vertices from the closed neighborhood of <em>v</em> in <em>S</em> as in <em>V</em>-<em>S</em>, then <em>S</em> is a <em>strong defensive alliance</em>. A (strong) defensive alliance is called <em>global</em> if it is also a dominating set of <em>G</em>. The <em>alliance partition number</em> (respectively, <em>strong alliance partition number</em>) is the maximum cardinality of a partition of <em>V</em> into defensive alliances (respectively, strong defensive alliances). The <em>global (strong) alliance partition number</em> 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.</p>","abstract_has_math":false,"creators":["Lachniet, Jason"],"institution":null,"degree_name":"MS (Master of Science)","degree_level":"Thesis - unrestricted","degree_discipline":"Mathematical Sciences","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007-05-05T07:00:00Z","date_published":"2007-05-05T07:00:00Z","updated_at":"2026-07-24T02:21:19Z","subjects":["domination","alliance partition","defensive alliance","graph theory","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"],"languages":[],"rights":["Copyright by the authors."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://dc.etsu.edu/etd/2080","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Lachniet, Jason"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2007-05-05T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematical Sciences"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis - unrestricted"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS (Master of Science)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["domination","alliance partition","defensive alliance","graph theory","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Copyright by the authors."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://dc.etsu.edu/context/etd/article/3441/viewcontent/LachnietJ041007f.PDF","https://dc.etsu.edu/etd/2080"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["Alliance Partitions in Graphs."]}]}],"canonical_facts":{"dc:creator":["Lachniet, Jason"],"dc:date.issued":["2007-05-05T07:00:00Z"],"dc:description.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.
"],"dc:identifier":["https://dc.etsu.edu/context/etd/article/3441/viewcontent/LachnietJ041007f.PDF","https://dc.etsu.edu/etd/2080"],"dc:rights":["Copyright by the authors."],"dc:subject":["domination","alliance partition","defensive alliance","graph theory","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"],"dc:title":["Alliance Partitions in Graphs."],"thesis:degree_discipline":["Mathematical Sciences"],"thesis:degree_level":["Thesis - unrestricted"],"thesis:degree_name":["MS (Master of Science)"]},"updated_at":"2026-07-24T02:21:19Z"}