کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420712 | 683972 | 2009 | 8 صفحه PDF | دانلود رایگان |
An offensive alliance in a graph Γ=(V,E)Γ=(V,E) is a set of vertices S⊂VS⊂V where for each vertex vv in its boundary the majority of vertices in vv’s closed neighborhood are in SS. In the case of strong offensive alliance, strict majority is required. An alliance SS is called global if it affects every vertex in V∖SV∖S, that is, SS is a dominating set of ΓΓ. The global offensive alliance number γo(Γ)γo(Γ) is the minimum cardinality of a global offensive alliance in ΓΓ. An offensive alliance is connected if its induced subgraph is connected. The global-connected offensive alliance number , γco(Γ)γco(Γ), is the minimum cardinality of a global-connected offensive alliance in ΓΓ.In this paper we obtain several tight bounds on γo(Γ)γo(Γ) and γco(Γ)γco(Γ) in terms of several parameters of ΓΓ. The case of strong alliances is studied by analogy.
Journal: Discrete Applied Mathematics - Volume 157, Issue 2, 28 January 2009, Pages 219–226