Narzędzia
Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

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. University of Blida LAMDA-RO Laboratory, Department of Mathematics B.P. 270, Blida, Algeria, m_chellali@yahoo.com [M. Chellali]
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