Security and secure-dominating sets in graphs

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.