Bounds on a graph's security number

    Authors

    R. D. Dutton; R. Lee;R. C. Brigham

    Comments

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

    Abbreviated Journal Title

    Discret Appl. Math.

    Keywords

    defensive alliances; secure sets; extremal graphs; 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 is an element of 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, not just singletons, can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. The security number s(G) of G is the cardinality of a smallest secure set. Bounds on s(G) are presented. Published by Elsevier B.V.

    Journal Title

    Discrete Applied Mathematics

    Volume

    156

    Issue/Number

    5

    Publication Date

    1-1-2008

    Document Type

    Article

    Language

    English

    First Page

    695

    Last Page

    704

    WOS Identifier

    WOS:000254161000013

    ISSN

    0166-218X

    Share

    COinS