Protection of a network by complete secure domination

Abstract

A complete secure dominating set of a graph $G$ is a dominating set $D \subseteq V(G)$ with the property that for each $v \in D$, there exists $F=\lbrace v_{j} \vert v_{j} \in N(v) \cap (V(G)-D)\rbrace$, such that for each $v_{j} \in F$, $( D-\lbrace v \rbrace) \cup \lbrace v_{j} \rbrace$ is a dominating set. The minimum cardinality of any complete secure dominating set is called the complete secure domination number of $G$ and is denoted by $\gamma_{csd}(G)$. In this paper, the bounds for complete secure domination number for some standard graphs like grid graphs and stacked prism graphs in terms of number of vertices of $G$ are found and also the bounds for the complete secure domination number of a tree are obtained in terms of different parameters of $G$.

Keywords

• Domination
• Secure domination
• Complete secure domination

References

1. [1] V. Anandam, Harmonic functions and potentials on finite and infinite networks, Springer, Heidelberg, Bologna (2011).
2. [2] S. Axler, P. Bourdon, W. Ramey, Harmonic function theory, Springer-Verlag, New York (2001).
3. [3] N. L. Biggs, Discrete mathematics, Clarendon Press, Oxford University Press, New York (1985).
4. [4] P. Cartier, Fonctions harmoniques sur un arbre, Sympos. Math. 9 (1972) 203–270.
5. [5] J. M. Cohen, F. Colonna, The Bloch space of a homogeneous tree, Bol. Soc. Mat. Mex. 37 (1992) 63–82.
6. [6] E. Nelson, A proof of Liouville’s theorem, Proc. Amer. Math. Soc. 12(6) (1961) 995.
7. [7] W. Woess, Random walks on infinite graphs and groups, Cambridge University Press (2000).