Mathematical Researches

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

---

Let  be a simple graph with vertex set  and edges set . A set  is a dominating
set if every vertex in  is adjacent to at least one vertex  in . An eternal 1-secure set of a graph G is defined as a dominating set  such that for any positive integer k and any sequence  of vertices, there exists a sequence of guards   with  and either  or  and  is a dominating set. If we take a guard on every vertex in an eternal 1-secure set, then for any sequence of attacks to vertices of the graph only by moving one guard during one of the edges adjacent with the vertex, the result set still remains secure. Now let for every sequence of attacks to vertices, all guards could move during one of the edges adjacent with the vertex and the result set still remains secure. This set is called eternal -  secure set. The eternal -  security number  is defined as the minimum number of an eternal - secure set. secure set in G. An edge  is subdivided if the edge  is deleted and a new vertex  is added, along with two new edges and . The eternal - security subdivision number  of a graph  is the minimum cardinality of a set of edges that must be subdivided (where each edge in  can be subdivided at most once) in order to increase the eternal - security number of  to increase the eternal m- security number of G. In this paper, we show that the eternal - security subdivision number is at most 3 for any nontrivial graph .
 

Keywords: eternal m- secure set, eternal m- security number, eternal m- security subdividion number

Full-Text [PDF 1274 kb]   (448 Downloads)    

Add your comments about this article : Your username or Email:

---

---