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

https://hal.inria.fr/hal-01196864
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
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

File

dmtcs-17-1-8.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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

Share

Metrics

Record views

70

Files downloads

731