Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
153--159
Opis fizyczny
Bibliogr. 7 poz., rys.
Twórcy
autor
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-AGHT-0005-0001