Global offensive k-alliance in bipartite graphs

• Autorzy: Chellali M. , Volkmann L.
• Języki publikacji: EN

Abstrakty

EN

Let k ≥ 0 be an integer. A set S of vertices of a graph G = (V (G), E(G)) is called a global offensive k-alliance if /N(v) ∩ S/ ≥ /N(v) - S/ + k for every v ∈ V (G) - S, where 0 ≤ k Δ and Δ is the maximum degree of G. The global offensive k-alliance number [formula] is the minimum cardinality of a global offensive k-alliance in G. We show that for every bipartite graph G and every integer k ≥ 2, [formula], where Lk(G) is the set of vertices of degree at most k - 1. Moreover, extremal trees attaining this upper bound are characterized.

Słowa kluczowe

EN

global offensive k-alliance number; bipartite graphs; trees

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2012
• Tom: Vol. 32, no. 1
• Strony: 83--89
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Chellali M.

autor

Volkmann L.

• University of Blida LAMDA-RO Laboratory, Department of Mathematics B.P. 270, Blida, Algeria,

Bibliografia

• [1] M. Blidia, M. Chellali, L. Volkmann, Some bounds on the p-domintion number in trees, Discrete Math. 306 (2006), 2031–2037.
• [2] M. Chellali, Offensive alliances in bipartite graphs, J. Combin. Math. Combin. Comput. 73 (2010), 245–255.
• [3] P. Kristiansen, S.M. Hedetniemi, S.T. Hedetniemi, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004), 157–177.
• [4] K.H. Shafique, R.D. Dutton, Maximum alliance-free and minimum alliance-cover sets, Congr. Numer. 162 (2003), 139–146.
• [5] K.H. Shafique, R. Dutton, A tight bound on the cardinalities of maximum alliance-free and minimum alliance-cover sets, J. Combin. Math. Combin. Comput. 56 (2006), 139–145.