Global alliances and independence in trees

Abstract

A global defensive (respectively, offensive) 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 (respectively, in V -S) at least half the vertices from the closed neighborhood of v are in S. These alliances are called strong if a strict majority of vertices from the closed neighborhood of v must be in S.