Geodesic
Bounds concerning the alliance number
Mathematica Bohemica, Tome 134 (2009) no. 4, pp. 387-398

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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$.
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$.
DOI : 10.21136/MB.2009.140671
Classification : 05C69
Keywords: defensive alliance; global defensive alliance; domination number 
Bullington, Grady; Eroh, Linda; Winters, Steven J. Bounds concerning the alliance number. Mathematica Bohemica, Tome 134 (2009) no. 4, pp. 387-398. doi: 10.21136/MB.2009.140671
@article{10_21136_MB_2009_140671,
     author = {Bullington, Grady and Eroh, Linda and Winters, Steven J.},
     title = {Bounds concerning the alliance number},
     journal = {Mathematica Bohemica},
     pages = {387--398},
     year = {2009},
     volume = {134},
     number = {4},
     doi = {10.21136/MB.2009.140671},
     mrnumber = {2597234},
     zbl = {1212.05186},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2009.140671/}
}
TY  - JOUR
AU  - Bullington, Grady
AU  - Eroh, Linda
AU  - Winters, Steven J.
TI  - Bounds concerning the alliance number
JO  - Mathematica Bohemica
PY  - 2009
SP  - 387
EP  - 398
VL  - 134
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2009.140671/
DO  - 10.21136/MB.2009.140671
LA  - en
ID  - 10_21136_MB_2009_140671
ER  - 
%0 Journal Article
%A Bullington, Grady
%A Eroh, Linda
%A Winters, Steven J.
%T Bounds concerning the alliance number
%J Mathematica Bohemica
%D 2009
%P 387-398
%V 134
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2009.140671/
%R 10.21136/MB.2009.140671
%G en
%F 10_21136_MB_2009_140671

[1] Kristiansen, P., Hedetniemi, S. M., Hedetniemi, S. T.: Alliances in graphs. J. Comb. Math. Comb. Comput. 48 (2004), 157-177. | MR | Zbl

[2] Haynes, T. W., Hedetniemi, S. T., Henning, M. A.: Global defensive alliances in graphs. Electron. J. Comb. 10 (2003), \# R47. | DOI | MR | Zbl

Cité par Sources :