Article ID Journal Published Year Pages File Type
421137 Discrete Applied Mathematics 2014 13 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,