Offensive alliances in cubic graphs

An offensive alliance in a graph $Γ=(V,E)$ is a set of vertices $S\subset V$ where for every vertex $v$ in its boundary it holds that the majority of vertices in $v$'s closed neighborhood are in $S$. In the case of strong offensive alliance, strict majority is required. An alliance $S$ is called global if it affects every vertex in $V\backslash S$, that is, $S$ is a dominating set of $Γ$. The global offensive alliance number $γ_o(Γ)$ (respectively, global strong offensive alliance number $γ_{\hat{o}}(Γ)$) is the minimum cardinality of a global offensive (respectively, global strong offensive) alliance in $Γ$. If $Γ$ has global independent offensive alliances, then the \emph{global independent offensive alliance number} $γ_i(Γ)$ is the minimum cardinality among all independent global offensive alliances of $Γ$. In this paper we study mathematical properties of the global (strong) alliance number of cubic graphs. For instance, we show that for all connected cubic graph of order $n$, $\frac{2n}{5}\le γ_i(Γ)\le \frac{n}{2}\le γ_{\hat{o}}(Γ)\le \frac{3n}{4} \le γ_{\hat{o}}({\cal L}(Γ))=γ_{o}({\cal L}(Γ))\le n,$ where ${\cal L}(Γ)$ denotes the line graph of $Γ$. All the above bounds are tight.

No reviews yet.

No comments yet.