Title

Bounds on a graph's security number

Authors

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