Offensive alliances in cubic graphs

Abstract

An offensive alliance in a graph $\Gamma =(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 $\Gamma$. The global offensive alliance number ${\gamma }_o(\Gamma )$ (respectively, global strong offensive alliance number ${\gamma }_{\hat{o}}(\Gamma )$) is the minimum cardinality of a global offensive (respectively, global strong offensive) alliance in $\Gamma$. If $\Gamma$ has global independent offensive alliances, then the \emph{global independent offensive alliance number} ${\gamma }_i(\Gamma )$ is the minimum cardinality among all independent global offensive alliances of $\Gamma$. 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 {\gamma }_i(\Gamma )\le \frac{n}{2}\le {\gamma }_{\hat{o}}(\Gamma )\le \frac{3n}{4}\le {\gamma }_{\hat{o}}(\mathcal{L}(\Gamma ))={\gamma }_o(\mathcal{L}(\Gamma ))\le n,$$ where $\mathcal{L}(\Gamma )$ denotes the line graph of $\Gamma$. All the above bounds are tight.