| dc.description.abstract | All graphs in this paper are finite and simple. Let G = (V;E) be a graph, x an element of V and
S a subset of V. Following convention, we let N(x) := {u : where ux is an element of E} and N[x] := {x}union N(x). For
S, N(S) is the union of the N(x),such that x is an element of S, and N[S] = N(S)union S. Security in graphs was first defined
by Brigham, Dutton, and Hedetniemi in 2007 (BDH), [1]. Given a graph G = (V;E) an
attack on S = {s_1, s_2, ...,s_k}, S a subset of V, is defined to be a collection of pairwise disjoint sets
A = {A_1,A_2, ...,A_k} for which A_i is a subset of N[s_i]- S, i = 1,...,k. A defense of S is a collection of
pairwise disjoint sets D = {D_1,D_2, ...,D_k} such that D_i is a subset of the intersection of N[s_i]and S, i = 1, ..,k. An attack
A is defendable if there is a defense D such that |D_i|is greater than or equal to |A_i| for i = 1, ...,k. We say that D
defends against A, in this case. S is secure if there is a defense of S against every attack
on S.
In Chapter 2 we give an efficient algorithm for finding a defense against an attack, when
one exists. In Chapter 3 we give some fundamental results about secure-dominating sets in
graphs, and determine the minimum order of a secure-dominating set in paths, cycles, and
complete multipartite graphs. In Chapter 4 we give efficient tests for the security of S when
G[S], the subgraph of G induced by S, satisfies certain conditions. | en_US |
