Offensive r-alliances in graphs

Abstract: Let

G = (V, E)

be a simple graph. For a nonempty set

X s u b s e t V,

and a vertex

v i n V,

d e l t a_{X} (v)

denotes the number of neighbors

v

has in

X .

A nonempty set

S s u b s e t V

is an emph{offensive

r

-alliance} in

G

if

f o r a l l v i n p a r t i a l (S),

where

p a r t i a l (S)

denotes the boundary of

S

. An offensive

r

-alliance

S

is called emph{global} if it forms a dominating set. The emph{global offensive

r

-alliance number} of

G

, denoted by

g a m m a_{r}^{o} (G)

, is the minimum cardinality of a global offensive

r

-alliance in

G

. We show that the problem of finding optimal (global) offensive

r

-alliances is NP-complete and we obtain several tight bounds on

g a m m a_{r}^{o} (G)

.

Recommendations

Cites work

Cited in

(27)

This page was built for publication: Offensive \(r\)-alliances in graphs