Grady Bullington, Linda Eroh, Steven J. Winters, Mathematics Department, University of Wisconsin Oshkosh, 800 Algoma Blvd., Oshkosh, WI, 54901, USA, e-mail: bullingt@uwosh.edu, eroh@uwosh.edu, winters@uwosh.edu
Abstract: 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 $\order(H_1) \leq\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$.
Keywords: defensive alliance, global defensive alliance, domination number
Classification (MSC 2000): 05C69
Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
