Global alliances and independent domination in some classes of graphs (Q1010858)

Summary: A dominating set \(S\) of a graph \(G\) is a global (strong) defensive alliance if for every vertex \(v\in S\), the number of neighbors \(v\) has in \(S\) plus one is at least (greater than) the number of neighbors it has in \(V\setminus S\). The dominating set \(S\) is a global (strong) offensive alliance if for every vertex \(v\in V\setminus S\), the number of neighbors \(v\) has in \(S\) is at least (greater than) the number of neighbors it has in \(V\setminus S\) plus one. The minimum cardinality of a global defensive (strong defensive, offensive, strong offensive) alliance is denoted by \(\gamma_a(G) (\gamma_{\hat a}(G), \gamma_o(G), \gamma_{\hat o}(G))\). We compare each of the four parameters \(\gamma_a, \gamma_{\hat a}, \gamma_o, \gamma_{\hat o}\) to the independent domination number \(i\). We show that \(i(G)\leq \gamma ^2_a(G)-\gamma_a(G)+1\) and \(i(G)\leq \gamma_{\hat{a}}^2(G)-2\gamma_{\hat{a}}(G)+2\) for every graph; \(i(G)\leq \gamma ^2_a(G)/4 +\gamma_a(G)\) and \(i(G)\leq \gamma_{\hat{a}}^2(G)/4 +\gamma_{\hat{a}}(G)/2\) for every bipartite graph; \(i(G)\leq 2\gamma_a(G)-1\) and \(i(G)=3\gamma_{\hat{a}}(G)/2 -1\) for every tree and describe the extremal graphs; and that \(\gamma_o(T)\leq 2i(T)-1\) and \(i(T)\leq \gamma_{\hat o}(T)-1\) for every tree. We use a lemma stating that \(\beta(T)+2i(T)\geq n+1\) in every tree \(T\) of order \(n\) and independence number \(\beta(T)\).