Burger, Anton Pierre and Villiers, Alewyn Petrus, and Vuuren, Jan Harm, - 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 domination

Authors: Burger, Anton Pierre and Villiers, Alewyn Petrus, and Vuuren, Jan Harm,

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.


Source : oai:HAL:hal-01196864v1
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]


Share

Browsing statistics

This page has been seen 23 times.
This article's PDF has been downloaded 110 times.