Co-secure and secure domination in graphs

Title: Co-secure and secure domination in graphs
Creator: Arumugam, S.; Ebadi, Karam; Manrique, Martin
Relation: Utilitas Mathematica Vol. 94, p. 167-182
Publisher: University of Manitoba, Department of Computer Science
Resource Type: journal article
Date: 2014
Description: A set S ⊆ V is a co-secure dominating set (CSDS) of a graph G = (V, E) if S is a dominating set, and for each u ∈ S there exists a vertex ∈ VS such that uv ∈ E and (S{u}) U {v} is a dominating set. The minimum cardinality of a co-secure dominating set in G is the co-secure domination number γcs(G) of G. In this paper we initiate a study of this parameter. We determine the co-secure domination number of some families of standard graphs and obtain sharp bounds. We also prove that the decision problem for this parameter is NP-complete even when restricted to bipartite, chordal or planar graphs. A set S ⊆ V is a secure dominating set of a graph G = (V, E) if for each u ∈ VS there exists a vertex v ∈ S such that uv ∈ E and (S{v})U {u} is a dominating set. The minimum cardinality of a secure dominating set in G is the secure domination number γs(G) of G. We present a few basic results on this parameter.
Identifier: http://hdl.handle.net/1959.13/1306230
Identifier: uon:21172
Identifier: ISSN:0315-3681
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format