Advances and Applications in Discrete Mathematics
Volume 18, Issue 1, Pages 33 - 44
(January 2017) http://dx.doi.org/10.17654/AADMJan2017_033_044 |
|
ABOUT SECURE INDEPENDENCE IN GRAPHS
D. K. Thakkar, B. M. Kakrecha and A. A. Prajapati
|
Abstract: In this paper, we introduce a new concept called secure independent set, which is defined as follows: an independent set S of the graph G is said to be secure independent set if for every v in S, there is a vertex u outside S such that u is adjacent to v and is an independent set. Every secure independent set is an independent set but an independent set need not be a secure independent set. We have proved that among the collection of all independent sets of the graph with equal cardinality, if there is at least one independent set which is also a secure independent set, then the intersection of all independent sets of the collection is empty. The cardinality of a maximum secure independent set is the secure independence number of the graph. A necessary and sufficient condition is proved under which the secure independence number of the graph decreases when a vertex is removed from the graph. We have also defined a strongly secure independent set. A secure independent set S is said to be strongly secure independent set if for every v in S, there is a vertex u outside S such that u is adjacent to v and is a secure independent set. A necessary and sufficient condition under which a secure independent set is a strongly secure independent set has been proved. |
Keywords and phrases: independent set, independence number, secure independent set, secure independence number, strongly secure independent set, strongly secure independence number. |
|
Number of Downloads: 319 | Number of Views: 1119 |
|