A note on global alliances in trees

• Autorzy: Bouzefrane M. , Chellali M.
• 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,

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.