Keywords

Algorithms, Computational complexity, Domination (Graph theory), Graph theory, NP complete problems, Trees (Graph theory)

Abstract

Let G = (V, E) be a graph and let S ⊆ V be a subset of vertices. The set S is a defensive alliance if for all x ∈ S, |N[x] ∩ S| ≥ |N[x] − S|. The concept of defensive alliances was introduced in [KHH04], primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if any one of them is attacked. For a vertex x in a defensive alliance, the number of neighbors of x inside the alliance, plus the vertex x, is at least the number of neighbors of x outside the alliance. In a graph model, the vertices of a graph represent nations and the edges represent country boundaries. Thus, if the nation corresponding to a vertex x is attacked by its neighbors outside the alliance, the attack can be thwarted by x with the assistance of its neighbors in the alliance. In a different subject matter, [FLG00] applies graph theory to model the world wide web, where vertices represent websites and edges represent links between websites. A web community is a subset of vertices of the web graph, such that every vertex in the community has at least as many neighbors in the set as it has outside. So, a web community C satisfies ∀x ∈ C, |N[x] ∩ C| > |N[x] − C|. These sets are very similar to defensive alliances. They are known as strong defensive alliances in the literature of alliances in graphs. Other areas of application for alliances and related topics include classification, data clustering, ecology, business and social networks. iii Consider the application of modeling nations in times of war introduced in the first paragraph. In a defensive alliance, any attack on a single member of the alliance can be successfully defended. However, as will be demonstrated in Chapter 1, a defensive alliance may not be able to properly defend itself when multiple members are under attack at the same time. The concept of secure sets is introduced in [BDH07] for exactly this purpose. The non-empty set S is a secure set if every subset X ⊆ S, with the assistance of vertices in S, can successfully defend against simultaneous attacks coming from vertices outside of S. The exact definition of simultaneous attacks and how such attacks may be defended will be provided in Chapter 1. In [BDH07], the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A non-empty set S is a secure set if and only if ∀X ⊆ S, |N[X] ∩ S| ≥ |N[X] − S| ([BDH07], Theorem 11). The cardinality of a minimum secure set is the security number of G, denoted s(G). A secure set S is a global secure set if it further satisfies N[S] = V . The cardinality of a minimum global secure set of G is the global security number of G, denoted γs(G). In this work, we present results on secure sets and global secure sets. In particular, we treat the computational complexity of finding the security number of a graph, present algorithms and bounds for the global security numbers of trees, and present the exact values of the global security numbers of paths, cycles and their Cartesian products.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

2011

Semester

Summer

Advisor

Dutton, Ronald

Degree

Doctor of Philosophy (Ph.D.)

College

College of Engineering and Computer Science

Department

Electrical Engineering and Computer Science

Format

application/pdf

Identifier

CFE0003888

URL

http://purl.fcla.edu/fcla/etd/CFE0003888

Language

English

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Subjects

Dissertations, Academic -- Engineering and Computer Science, Engineering and Computer Science -- Dissertations, Academic

Download

Share

COinS