Global defensive alliances of trees and Cartesian product of paths and cycles

Abstract: Given a graph , a defensive alliance of is a set of vertices satisfying the condition that for each , at least half of the vertices in the closed neighborhood of are in . A defensive alliance is called global if every vertex in is adjacent to at least one member of the defensive alliance . The global defensive alliance number of , denoted , is the minimum size around all the global defensive alliances of . In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete -ary trees for . We also establish upper bounds and lower bounds for and , and show that the bounds are sharp for certain . [Copyright &y& Elsevier]