Global alliances and independent domination in some classes of graphs

Odile Favaron

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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)\le \gamma ^2_a(G)-\gamma_a(G)+1$ and $i(G)\le \gamma_{\hat{a}}^2(G)-2\gamma_{\hat{a}}(G)+2$ for every graph; $i(G)\le \gamma ^2_a(G)/4 +\gamma_a(G)$ and $i(G)\le \gamma_{\hat{a}}^2(G)/4 +\gamma_{\hat{a}}(G)/2$ for every bipartite graph; $i(G)\le 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)\le 2i(T)-1$ and $i(T)\le \gamma_{\hat o}(T)-1$ for every tree. We use a lemma stating that $\beta(T)+2i(T)\ge n+1$ in every tree $T$ of order $n$ and independence number $\beta(T)$.

Détail

DOI : 10.37236/847

Classification : 05C69
Mots-clés : dominating set, global defensive alliance, strong defensive alliance, global offensive alliance, strong offensive alliance, independent domination number, extremal graphs