Offensive alliances in graphs | Zendy

Odile Favaron | Zendy; Gerd H. Fricke | Zendy; Wayne Goddard | Zendy; Sandra M. Hedetniemi | Zendy; Stephen T. Hedetniemi | Zendy; Petter Kristiansen | Zendy; R. Duane Skaggs | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Offensive alliances in graphs

Author(s) -

Odile Favaron,

Gerd H. Fricke,

Wayne Goddard,

Sandra M. Hedetniemi,

Stephen T. Hedetniemi,

Petter Kristiansen,

R. Duane Skaggs

Publication year - 2004

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1230

Subject(s) - offensive , mathematics , combinatorics , operations research

A set S is an offensive alliance if for every vertex v in its boundary N(S)−S it holds that the majority of vertices in v’s closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number is at most 5/6 the order.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research