The alliance partition number of grid graphs

Abstract

For a graph G = (V, E), a non-empty subset S⊆V is called a defensive alliance if for each v∊S, there are at least as many vertices from the closed neighborhood of v in S as in V-S. The alliance partition number is the maximum cardinality of a partition of V into defensive alliances. We determine the alliance partition number of grid graphs.

Keywords:

• defensive alliance
• alliance partition
• alliance partition number
• grid graphs

2000 Mathematics Subject Classification:

• 05C