PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2012 | 10 | 3 | 1113-1124
Tytuł artykułu

Bounds on global secure sets in cactus trees

Treść / Zawartość
Warianty tytułu
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
Wydawca
Czasopismo
Rocznik
Tom
10
Numer
3
Strony
1113-1124
Opis fizyczny
Daty
wydano
2012-06-01
online
2012-03-24
Twórcy
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
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-012-0035-5
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.