Bounds concerning the alliance number

Bullington, Grady ; Eroh, Linda ; Winters, Steven J.

Mathematica Bohemica, Tome 134 (2009) no. 4, pp. 387-398.

Résumé

P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi, in Alliances in graphs, J.\ Combin.\ Math.\ Combin.\ Comput.\ 48 (2004), 157--177, and T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, in Global defensive alliances in graphs, Electron.\ J.\ Combin.\ 10 (2003), introduced the defensive alliance number $a(G)$, strong defensive alliance number $\hat a(G)$, and global defensive alliance number $\gamma _a(G)$. In this paper, we consider relationships between these parameters and the domination number $\gamma (G)$. For any positive integers $a,b,$ and $c$ satisfying $a \leq c$ and $b \leq c$, there is a graph $G$ with $a=a(G)$, $b=\gamma (G)$, and $c=\gamma _a(G)$. For any positive integers $a,b,$ and $c$, provided $a \leq b \leq c$ and $c$ is not too much larger than $a$ and $b$, there is a graph $G$ with $\gamma (G)=a$, $\gamma _a(G)=b$, and $\gamma _{\hat a}(G)=c$. Given two connected graphs $H_1$ and $H_2$, where $\mathop{\rm order}(H_1) \leq \mathop{\rm order}(H_2)$, there exists a graph $G$ with a unique minimum defensive alliance isomorphic to $H_1$ and a unique minimum strong defensive alliance isomorphic to $H_2$.

Détail

DOI : 10.21136/MB.2009.140671

Classification : 05C69
Keywords: defensive alliance; global defensive alliance; domination number