Alliance Partitions in Graphs.

<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>

Name thesis:degree_name

MS (Master of Science)

Level thesis:degree_level

Thesis - unrestricted

Discipline thesis:degree_discipline

Mathematical Sciences

Year dc:date.issued

2007

Author dc:creator

• Lachniet, Jason

• domination
• alliance partition
• defensive alliance
• graph theory
• Discrete Mathematics and Combinatorics
• Mathematics
• Physical Sciences and Mathematics

Statement dc:rights

• Copyright by the authors.

Repository record dc:identifier

https://dc.etsu.edu/etd/2080

OAI identifier oai:identifier

oai:dc.etsu.edu:etd-3441