Skip to Main content Skip to Navigation
Journal articles

Edge stability in secure graph domination

Abstract : A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X-v)∪u is again a dominating set of G. The secure domination number of G is the cardinality of a smallest secure dominating set of G. A graph G is p-stable if the largest arbitrary subset of edges whose removal from G does not increase the secure domination number of the resulting graph, has cardinality p. In this paper we study the problem of computing p-stable graphs for all admissible values of p and determine the exact values of p for which members of various infinite classes of graphs are p-stable. We also consider the problem of determining analytically the largest value ωn of p for which a graph of order n can be p-stable. We conjecture that ωn=n-2 and motivate this conjecture.
Document type :
Journal articles
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, September 10, 2015 - 3:17:28 PM
Last modification on : Thursday, September 7, 2017 - 1:03:43 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:03:04 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01196864, version 1



Anton Pierre Burger, Alewyn Petrus Villiers, Jan Harm Vuuren. Edge stability in secure graph domination. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.103--122. ⟨hal-01196864⟩



Record views


Files downloads