Akademska digitalna zbirka SLovenije - logo
E-resources
Full text
Peer reviewed
  • The secure domination probl...
    Jha, Anupriya; Pradhan, D.; Banerjee, S.

    Information processing letters, 20/May , Volume: 145
    Journal Article

    •We study the secure domination problem in cographs.•The secure domination problem is NP-hard for circle graphs.•An O(n+m) time algorithm is proposed to find the secure domination number of a given cograph. Let G=(V,E) be a graph. A subset D of vertices of G is called a dominating set of G if for every u∈V∖D, there exists a vertex v∈D such that uv∈E. A dominating set D of a graph G is called a secure dominating set of G if for every u∈V∖D, there exists a vertex v∈D such that uv∈E and (D∖{v})∪{u} is a dominating set of G. The secure domination number of G, denoted by γs(G), is the minimum cardinality of a secure dominating set of G. In this paper, we present an O(n+m) time algorithm to compute the secure domination number of a cograph having n vertices and m edges.