Bounds on global secure sets in cactus trees

• Autorzy: Katarzyna Jesse-Józefczyk
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Graph; Alliance; Secure set; Dominating set; Cactus tree

Kategorie tematyczne

• 05C05: Trees
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2012
• Tom: 10
• Numer: 3
• Strony: 1113-1124

Daty

wydano

2012-06-01

online

2012-03-24

Twórcy

autor

Katarzyna Jesse-Józefczyk

• University of Zielona Góra

Bibliografia

• [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
• [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
• [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
• [4] Eroh L., Gera R., Global alliance partition in trees, J. Combin. Math. Combin. Comput., 2008, 66, 161–169
• [5] Haynes T.W., Hedetniemi S.T., Henning M.A., Global defensive alliances in graphs, Electron. J. Combin., 2003, 10(1), #R47
• [6] Kristiansen P., Hedetniemi S.M., Hedetniemi S.T., Alliances in graphs, J. Combin. Math. Combin. Comput., 2004, 48, 157–177

Identyfikatory

DOI

10.2478/s11533-012-0035-5