Strong Alliances in Graphs

Abstract

For any simple connected undirected graph $G=(V,E)$, a \textit{defensive alliance} is a subset $S$ of $V$ satisfying the condition that every vertex $v\in S$ has at most one more neighbour in $V-S$ than it has in $S$. The minimum cardinality of any defensive alliance in $G$ is called the \textit{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$-\textit{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.

Keywords

• Alliances
• Defensive alliances
• Secure sets