Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first last
cannonical link button

http://yadda.icm.edu.pl:80/baztech/element/bwmeta1.element.baztech-article-AGHT-0005-0001

Czasopismo

Opuscula Mathematica

Tytuł artykułu

A note on global alliances in trees

Autorzy Bouzefrane, M.  Chellali, M. 
Treść / Zawartość
Warianty tytułu
Języki publikacji EN
Abstrakty
EN For a graph G = (V,E), a set S ⊆ V is a dominating set if every vertex in V - S has at least a neighbor in S. A dominating set S is a global offensive (respectively, defensive) alliance if for each vertex in V - S (respectively, in S) at least half the vertices from the closed neighborhood of v are in S. The domination number γ (G) is the minimum cardinality of a dominating set of G, and the global offensive alliance number γo(G) (respectively, global defensive alliance number γa(G)) is the minimum cardinality of a global offensive alliance (respectively, global deffensive alliance) of G. We show that if T is a tree of order n, then γo(T) ≤ 2γ (T) - 1 and if n ≥ 3, then γo(T) ≤ 3/2?a(T) ? 1. Moreover, all extremal trees attaining the first bound are characterized.
Słowa kluczowe
EN global defensive alliance   global offensive alliance   domination   trees  
Wydawca AGH University of Science and Technology Press
Czasopismo Opuscula Mathematica
Rocznik 2011
Tom Vol. 31, no. 2
Strony 153--159
Opis fizyczny Bibliogr. 7 poz., rys.
Twórcy
autor Bouzefrane, M.
autor Chellali, M.
Bibliografia
[1] M. Chellali, Offensive alliances in bipartite graphs, J. Combin. Math. Combin. Comput., to appear.
[2] T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Global defensive alliances in graphs, Electron. J. Combin. 10 (2003) R47.
[3] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs,Marcel Dekker, New York, 1998.
[4] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[5] S.M. Hedetniemi, S.T. Hedetniemi, P. Kristiansen, Alliances in graphs, J. Combin. Math.Combin. Comput. 48 (2004), 157–177.
[6] O. Favaron, Global alliances and independent domination in some classes of graphs, Electron. J. Combin. 15 (2008) R123.
[7] M. Lemańska, Lower bound on the domination number of a tree, Discuss. Math. Graph Theory 24 (2004) 2, 165–169.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-AGHT-0005-0001
Identyfikatory