A global defensive alliance in a graph G = (V, E) is a set of vertices S ⊆ V with the properties that every vertex in V - S has at least one neighbor in S, and for each vertex v in S at least half the vertices from the closed neighborhood of v are in S. The alliance is called strong if a strict majority of vertices from the closed neighborhood of v are in S. The global defensive alliance number γa(G) (respectively, global strong defensive alliance number γâ(G)) is the minimum cardinality of a global defensive alliance (respectively, global strong defensive alliance) of G. We show that if T is a tree with order n ≥ 2, l leaves and s support vertices, then γâ (T) ≥ (3n - l - s + 4) /6 and γa (T) ≥ (3n - l - s + 4)/8. Moreover, all extremal trees attaining each bound are characterized.

No description available.

For a graph G = (V, E), a non-empty set S ⊆ V is a defensive alliance if for every vertex v in S, v has at most one more neighbor in V - S than it has in S, and S is an offensive alliance if for every v ∈ V - S that has a neighbor in S, v has more neighbors in S than in V - S. A powerful alliance is both defensive and offensive. We initiate the study of powerful alliances in graphs.

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.