You are here
GLOBAL SECURE SETS OF TREES AND GRIDLIKE GRAPHS
 Date Issued:
 2011
 Abstract/Description:
 Let G = (V, E) be a graph and let S be a subset of vertices. The set S is a defensive alliance if for all x in S, N intersect S >= N  S. The concept of defensive alliances was introduced in , primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if anyone 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, 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 for all x in C, N intersect C > N  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. 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 for exactly this purpose. The set S is a secure set if every subset X of 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 , the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A nonempty set S is a secure set if and only if for all subset X of S, N intersect S >= N  S (, 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 = V. The cardinality of a minimum global secure set of G is the global security number of G, denoted gs(G). In this work, we present results on secure sets and global secure sets. In particular, we present algorithms and bounds for the global security numbers of trees, and the exact values of the global security numbers of paths, cycles and their Cartesian products. Petter Kristiansen, Sandra M. Hedetniemi, and Stephen T. Hedetniemi. "Alliances in graphs." J. Combin. Math. Combin. Comput., 48:157177, 2004. G. W. Flake, S. Lawrence, and C. L. Giles. "Efficient identification of web communities." ACM SIGKDD, pp. 150160, 2000. Robert C. Brigham, Ronald D. Dutton, and Stephen T. Hedetniemi. "Security in graphs." Discrete Appl. Math., 155(13):17081714, 2007.
Title:  GLOBAL SECURE SETS OF TREES AND GRIDLIKE GRAPHS. 
11 views
6 downloads 

Name(s): 
Ho, Yiuyu, Author Dutton, Ronald, Committee Chair University of Central Florida, Degree Grantor 

Type of Resource:  text  
Date Issued:  2011  
Publisher:  University of Central Florida  
Language(s):  English  
Abstract/Description:  Let G = (V, E) be a graph and let S be a subset of vertices. The set S is a defensive alliance if for all x in S, N intersect S >= N  S. The concept of defensive alliances was introduced in , primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if anyone 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, 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 for all x in C, N intersect C > N  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. 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 for exactly this purpose. The set S is a secure set if every subset X of 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 , the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A nonempty set S is a secure set if and only if for all subset X of S, N intersect S >= N  S (, 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 = V. The cardinality of a minimum global secure set of G is the global security number of G, denoted gs(G). In this work, we present results on secure sets and global secure sets. In particular, we present algorithms and bounds for the global security numbers of trees, and the exact values of the global security numbers of paths, cycles and their Cartesian products. Petter Kristiansen, Sandra M. Hedetniemi, and Stephen T. Hedetniemi. "Alliances in graphs." J. Combin. Math. Combin. Comput., 48:157177, 2004. G. W. Flake, S. Lawrence, and C. L. Giles. "Efficient identification of web communities." ACM SIGKDD, pp. 150160, 2000. Robert C. Brigham, Ronald D. Dutton, and Stephen T. Hedetniemi. "Security in graphs." Discrete Appl. Math., 155(13):17081714, 2007.  
Identifier:  CFE0003888 (IID), ucf:48719 (fedora)  
Note(s): 
20110801 Ph.D. Engineering and Computer Science, School of Electrical Engineering and Computer Science Doctorate This record was generated from author submitted information. 

Subject(s): 
secure set security number dominating set tree gridlike graph Cartesian product algorithm complexity NPcompleteness bounds 

Persistent Link to This Record:  http://purl.flvc.org/ucf/fd/CFE0003888  
Restrictions on Access:  public  
Host Institution:  UCF 