Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421137 | Discrete Applied Mathematics | 2014 | 13 Pages |
Abstract
A secure set in a graph G=(V,E)G=(V,E) is a set of vertices S⊆VS⊆V such that for any subset X⊆SX⊆S, |N[X]∩S|≥|N(X)−S||N[X]∩S|≥|N(X)−S|. A global secure set SD⊆VSD⊆V is a secure set that is also a dominating set, i.e., N[SD]=VN[SD]=V. In this paper we investigate global secure sets that contain exactly half of the vertices of the graph. In particular we show that every hamiltonian claw-free cubic graph has such a global secure set. Moreover, we prove that in any claw-free cubic graph there is a global secure set that contains at most 5/95/9 of the vertices of the graph.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Katarzyna Jesse-Józefczyk, Elżbieta Sidorowicz,