Strong Alliances in Graphs

For any simple connected undirected graph G = (VƐE), a defensive al- liance is a subset S of V satisfying the condition that every vertex v 2 S has at most one more neighbour in V - S than it has in S. The minimum cardinality of any de- fensive alliance in G is called the alliance number of G, and is denoted by a_d(G). In this paper, we introduce a new type of alliance number called the k-strong alliance number and its varieties. The bounds for 1-strong alliance number in terms of different graphical parameters are determined and the characterizations of graphs with 1-strong alliance number 1, 2, and n are obtained.