Abstract

Let S ⊂ V (G) for a given simple non-empty graph G. We define for any nonempty subset X of S the predicate SECG,S(X) = true iff |NG[X]∩S| ≥ |NG[X]\S|. Let H be a non-empty family of graphs such that for each vertex v ∈ V (G) there is a subgraph H of G containing v and isomorphic to a member of H. We introduce the concept of H-alliance extending the concept of global defensive secure structures. By an H-alliance in a graph G we mean a set S ⊂ V (G) such that (1) each vertex v ∈ S belongs to a subgraph H of G that is isomorphic to a member of H, and (2) for each H ⊂ G[S] isomorphic to a member of H, SECG,S(V (H)) = true. If S is also a dominating set of G, we call it a global H-alliance of G. If H = {K1}, then such an H-alliance we call a defensive alliance (GA) [1] or a vertex alliance. If H = {K2}, then such an H-alliance we call an edge alliance [2]. In the case of H is a class of all complete graphs (i.e., K1, K2, . . .), then an H-alliance we call a complete alliance [3]. If H = {K1, . . . , Kk}, then an H-alliance we call k-complete alliance. In this talk we present general properties of global defensive secure structures (i.e., H-alliances), algorithms for H-alliance problems (exact and approximation ones), and we provide new N P-complete results for global defensive secure structures for bounded degree graphs. We formulate also H-alliance problem in some special cases as ILP problem and study a few algorithmic approaches.

Authors (2)