Bounds on global secure sets in cactus trees
Open Mathematics (2012)
- Volume: 10, Issue: 3, page 1113-1124
- ISSN: 2391-5455
Access Full Article
top
Abstract
topHow to cite
topKatarzyna Jesse-Józefczyk. "Bounds on global secure sets in cactus trees." Open Mathematics 10.3 (2012): 1113-1124. <http://eudml.org/doc/269551>.
@article{KatarzynaJesse2012,
abstract = {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.},
author = {Katarzyna Jesse-Józefczyk},
journal = {Open Mathematics},
keywords = {Graph; Alliance; Secure set; Dominating set; Cactus tree; graph; alliance; secure set; dominating set; cactus tree},
language = {eng},
number = {3},
pages = {1113-1124},
title = {Bounds on global secure sets in cactus trees},
url = {http://eudml.org/doc/269551},
volume = {10},
year = {2012},
}
TY - JOUR
AU - Katarzyna Jesse-Józefczyk
TI - Bounds on global secure sets in cactus trees
JO - Open Mathematics
PY - 2012
VL - 10
IS - 3
SP - 1113
EP - 1124
AB - 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.
LA - eng
KW - Graph; Alliance; Secure set; Dominating set; Cactus tree; graph; alliance; secure set; dominating set; cactus tree
UR - http://eudml.org/doc/269551
ER -
References
top- [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 Zbl1125.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 Zbl1113.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 Zbl1189.05123
- [4] Eroh L., Gera R., Global alliance partition in trees, J. Combin. Math. Combin. Comput., 2008, 66, 161–169 Zbl1160.05022
- [5] Haynes T.W., Hedetniemi S.T., Henning M.A., Global defensive alliances in graphs, Electron. J. Combin., 2003, 10(1), #R47 Zbl1031.05096
- [6] Kristiansen P., Hedetniemi S.M., Hedetniemi S.T., Alliances in graphs, J. Combin. Math. Combin. Comput., 2004, 48, 157–177 Zbl1051.05068
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.