Security in graphs

    Authors

    R. C. Brigham; R. D. Dutton;S. T. Hedetniemi

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Discret Appl. Math.

    Keywords

    alliances; defensive alliances; Mathematics, Applied

    Abstract

    Let G = (V, E) be a graph. A set S subset of V is a defensive alliance if vertical bar N[x] boolean AND S vertical bar > = vertical bar N[x] - S vertical bar for every x epsilon S. Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attack by its neighbors outside of S. An entire set S is secure if any subset X subset of S can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. Necessary and sufficient conditions for a set to be secure are determined. Published by Elsevier B.V.

    Journal Title

    Discrete Applied Mathematics

    Volume

    155

    Issue/Number

    13

    Publication Date

    1-1-2007

    Document Type

    Article

    Language

    English

    First Page

    1708

    Last Page

    1714

    WOS Identifier

    WOS:000249236300006

    ISSN

    0166-218X

    Share

    COinS