You are here

GLOBAL SECURE SETS OF TREES AND GRID-LIKE GRAPHS

Download pdf | Full Screen View

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 non-empty 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:157-177, 2004. G. W. Flake, S. Lawrence, and C. L. Giles. "Efficient identification of web communities." ACM SIGKDD, pp. 150-160, 2000. Robert C. Brigham, Ronald D. Dutton, and Stephen T. Hedetniemi. "Security in graphs." Discrete Appl. Math., 155(13):1708-1714, 2007.
Title: GLOBAL SECURE SETS OF TREES AND GRID-LIKE 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 non-empty 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:157-177, 2004. G. W. Flake, S. Lawrence, and C. L. Giles. "Efficient identification of web communities." ACM SIGKDD, pp. 150-160, 2000. Robert C. Brigham, Ronald D. Dutton, and Stephen T. Hedetniemi. "Security in graphs." Discrete Appl. Math., 155(13):1708-1714, 2007.
Identifier: CFE0003888 (IID), ucf:48719 (fedora)
Note(s): 2011-08-01
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
grid-like graph
Cartesian product
algorithm
complexity
NP-completeness
bounds
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFE0003888
Restrictions on Access: public
Host Institution: UCF

In Collections