Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for trees, and we relate them to the known bounds on the minimum cardinality of global defensive alliances.
@article{bwmeta1.element.doi-10_2478_s11533-012-0035-5,
author = {Katarzyna Jesse-J\'ozefczyk},
title = {Bounds on global secure sets in cactus trees},
journal = {Open Mathematics},
volume = {10},
year = {2012},
pages = {1113-1124},
zbl = {1239.05139},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-012-0035-5}
}
Katarzyna Jesse-Józefczyk. Bounds on global secure sets in cactus trees. Open Mathematics, Tome 10 (2012) pp. 1113-1124. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-012-0035-5/
[1] Brigham R.C., Dutton R.D., Hedetniemi S.T., Security in graphs, Discrete Appl. Math., 2007, 155(13), 1708–1714 http://dx.doi.org/10.1016/j.dam.2007.03.009 | Zbl 1125.05071
[2] Cami A., Balakrishnan H., Deo N., Dutton R.D., On the complexity of finding optimal global alliances, J. Combin. Math. Combin. Comput., 2006, 58, 23–31 | Zbl 1113.05074
[3] Chellali M., Haynes T.W., Global alliances and independence in trees, Discuss. Math. Graph Theory, 2007, 27(1), 27, 19–27 http://dx.doi.org/10.7151/dmgt.1340 | Zbl 1189.05123
[4] Eroh L., Gera R., Global alliance partition in trees, J. Combin. Math. Combin. Comput., 2008, 66, 161–169 | Zbl 1160.05022
[5] Haynes T.W., Hedetniemi S.T., Henning M.A., Global defensive alliances in graphs, Electron. J. Combin., 2003, 10(1), #R47 | Zbl 1031.05096
[6] Kristiansen P., Hedetniemi S.M., Hedetniemi S.T., Alliances in graphs, J. Combin. Math. Combin. Comput., 2004, 48, 157–177 | Zbl 1051.05068