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-AGHS-0001-0001

Czasopismo

Opuscula Mathematica

Tytuł artykułu

On the global offensive alliance number of a tree

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 alliance if for every vertex v in V - S, at least half of the vertices in its closed neighborhood 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) is the minimum cardinality of a global offensive alliance of G. We first show that every tree of order at least three with l leaves and s support vertices satisfies ϒo(T) ≥ (n - l + s + 1)/3 and we characterize extremal trees attaining this lower bound. Then we give a constructive characterization of trees with equal domination and global offensive alliance numbers.
Słowa kluczowe
EN global offensive alliance number   domination number   trees  
Wydawca AGH University of Science and Technology Press
Czasopismo Opuscula Mathematica
Rocznik 2009
Tom Vol. 29, no. 3
Strony 223--228
Opis fizyczny Bibliogr. 5 poz.
Twórcy
autor Bouzefrane, M.
autor Chellali, M.
Bibliografia
1] M. Chellali, O_ensive alliances in bipartite graphs, J. Combin. Math. Combin. Comput., to appear.
[2] O. Favaron, G. Fricke, W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, P. Kristiansen, R.C. Laskar, D.R. Skaggs, Offensive alliances in graphs, Discuss. Math. Graph Theory 24 (2004) 2, 263-275.
[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.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-AGHS-0001-0001
Identyfikatory