Bounds concerning the alliance number
| Autor: | Linda Eroh, Steven J. Winters, Grady D. Bullington |
|---|---|
| Rok vydání: | 2009 |
| Předmět: | |
| Zdroj: | Mathematica Bohemica. 134:387-398 |
| ISSN: | 2464-7136 0862-7959 |
| DOI: | 10.21136/mb.2009.140671 |
| Popis: | 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$. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|