Global o Ensive Alliance Numbers in Graphs With Emphasis on Trees

Document Type

Article

Publication Date

10-1-2009

Description

For a graph G =(V,E), a non-empty set S ⊆ V is a global offensive alliance if for every v ∈ V -S, at least half of the vertices from the closed neighborhood of v are in S.A set S ⊆ V is a global strong offensive alliance if for each vertex v ∈ V - S, a strict majority of the vertices of the closed neighborhood of v are in S. The cardinality of a minimum global (strong) offensive alliance of a graph G is called the global (strong) offensive alliance number of G. We determine bounds on the global offensive alliance and the global strong offensive alliance numbers of a graph, and characterize the trees achieving two of these lower bounds.

Share

COinS