Previous |  Up |  Next


Title: Bounds concerning the alliance number (English)
Author: Bullington, Grady
Author: Eroh, Linda
Author: Winters, Steven J.
Language: English
Journal: Mathematica Bohemica
ISSN: 0862-7959
Volume: 134
Issue: 4
Year: 2009
Pages: 387-398
Summary lang: English
Category: math
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$. (English)
Keyword: defensive alliance
Keyword: global defensive alliance
Keyword: domination number
MSC: 05C69
idZBL: Zbl 1212.05186
idMR: MR2597234
Date available: 2010-07-20T18:11:19Z
Last updated: 2013-09-20
Stable URL:
Reference: [1] Kristiansen, P., Hedetniemi, S. M., Hedetniemi, S. T.: Alliances in graphs.J. Comb. Math. Comb. Comput. 48 (2004), 157-177. Zbl 1064.05112, MR 2036749
Reference: [2] Haynes, T. W., Hedetniemi, S. T., Henning, M. A.: Global defensive alliances in graphs.Electron. J. Comb. 10 (2003), \# R47. Zbl 1031.05096, MR 2026883


Files Size Format View
MathBohem_134-2009-4_6.pdf 224.1Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo