Anton Pierre Burger ; Alewyn Petrus Villiers ; Jan Harm Vuuren - Edge stability in secure graph domination

dmtcs:2120 - Discrete Mathematics & Theoretical Computer Science, March 16, 2015, Vol. 17 no. 1 -
Edge stability in secure graph dominationArticle

Authors: Anton Pierre Burger 1; Alewyn Petrus Villiers 2; Jan Harm Vuuren 2

  • 1 Department of Logistics [Stellenbosch]
  • 2 Department of Industrial Engineering [Matieland]

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.

Volume: Vol. 17 no. 1
Section: Graph Theory
Published on: March 16, 2015
Submitted on: June 27, 2014
Keywords: Secure domination,graph protection,edge removal,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 362 times.
This article's PDF has been downloaded 598 times.