Strong domination number of a modified graph

Document Type : Original Article


1 Department of Mathematical Science, Yazd University, 89195-741, Yazd, Iran

2 Department of Informatics, University of Bergen, P.O. Box 7803, 5020 Bergen, Norway


Let $G=(V,E)$ be a simple graph. A set $D\subseteq V$ is a strong dominating set of $G$, if for every vertex $x\in V\setminus D$ there is a vertex $y\in D$ with $xy\in E(G)$ and $\deg(x)\leq \deg(y)$. The strong domination number $\gamma_{st}(G)$ is defined as the minimum cardinality of a strong dominating set. In this paper, we study the effects on $\gamma_{st}(G)$ when $G$ is modified by operations on vertices and edges of $G$.