Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
defensive alliance; global defensive alliance; domination number
defensive alliance; global defensive alliance; domination number
Summary:
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$.
References:
[1] Kristiansen, P., Hedetniemi, S. M., Hedetniemi, S. T.: Alliances in graphs. J. Comb. Math. Comb. Comput. 48 (2004), 157-177. MR 2036749 | Zbl 1064.05112
[2] Haynes, T. W., Hedetniemi, S. T., Henning, M. A.: Global defensive alliances in graphs. Electron. J. Comb. 10 (2003), \# R47. DOI 10.37236/1740 | MR 2026883 | Zbl 1031.05096
Search
Partner of
