Global dual \(k\)-alliance in cubic graphs (Q2926093)

Let \(G=(V,E)\) be a simple graph. For a nonempty set \(S\subseteq V\), \(\delta_S(v)\) denotes the number of neighbors of \(v\) in \(S\) and \(\overline{S}\) denotes the complement of \(S\) in \(V\). Moreover, the neighborhood of \(S\), denoted by \(\partial(S)\), is defined as the set of vertices of \(\overline{S}\) such that they are adjacent to at least one vertex in \(S\). For \(k\in \{-\Delta,\ldots, \Delta\}\), a nonempty set \(S\subseteq V\) is a defensive \(k\)-alliance in \(G\) if \(\delta_S(v)\geq\delta_{\overline{S}}(v)+ k\), for every \(v\in S\). Moreover, for \(k\in \{2-\Delta,\ldots, \Delta\}\), a nonempty set \(S\subseteq V\) is an offensive \(k\)-alliance in \(G\) if \(\delta_S(v)\geq\delta_{\overline{S}}(v)+ k\), for every \(v \in\partial(S)\). A powerful \(k\)-alliance is a set of vertices of the graph, which is both defensive \(k\)-alliance and offensive \((k + 2)\)-alliance. A (defensive, offensive or powerful) \(k\)-alliance is called global if it is a dominating set. For \(k\in \{-\Delta,\ldots,\Delta-2\}\), the global powerful \(k\)-alliance number (or global dual \(k\)-alliance number) of \(G\), denoted by \(\gamma_k^p(G)\), is defined as the minimum cardinality of a global powerful \(k\)-alliance in \(G\). The main results of this paper are: NEWLINENEWLINENEWLINE For any connected cubic graph \(G\) of order \(n\), \(\gamma_0^p(G)\geq \frac{3n}{4}\). NEWLINENEWLINENEWLINE For any connected cubic graph \(G\) of order \(n\), \(\gamma_{-1}^p(G)\geq \frac{n}{2}\).NEWLINENEWLINENEWLINE For any connected cubic graph \(G\) of order \(n\), \(\gamma_0^p(G)\leq \frac{7n}{8}\).NEWLINENEWLINENEWLINE \textit{I. G. Yero} and \textit{J. A. Rodríguez-Velázquez} [Graphs Comb. 28, No. 4, 575--583 (2012; Zbl 1256.05181)] proved the following result: Let \(G\) be a graph of maximum degree \(\Delta\) and minimum degree \(\delta\). If \(S\) is a global powerful \(k\)-alliance in \(G\), then \((\delta+k+2)|\overline{S}|\leq (\Delta-k)|S|.\)NEWLINENEWLINE\noindent As an immediate consequence we have \(\gamma_k^p(G)\geq \frac{\delta+k+2}{\Delta+\delta+2}n\).NEWLINENEWLINENEWLINE Let \(k\) be a positive integer. A subset \(S\) of \(V\) is a \(k\)-tuple dominating set of \(G\) if for every vertex \(v\in V\), \(|N[v]\cap S|\geq k\), that is, \(v\) is in \(S\) and has at least \(k-1\) neighbors in \(S\) or \(v\) is in \(V-S\) and has at least \(k\) neighbors in \(S\). The \(k\)-tuple domination number \(\gamma_{\times k}(G)\) is the minimum cardinality of a \(k\)-tuple dominating set of \(G\). It is well known that if \(G\) is a graph with minimum degree \(\delta(G)\geq k-1\), then \(\gamma_{\times k}(G)\geq\frac{kn}{\Delta+1}\). It is easy to see that if \(k\geq 3\) and \(G\) is a \(k\)-regular graph of order \(n\), then every global powerful \((k-3)\)-alliance of \(G\) is a \(k\)-tuple dominating set of \(G\) and hence \(\gamma_{k}^p(G)\geq \gamma_{\times k}(G)\geq\frac{kn}{\Delta+1}\).