Strong domination number of a modified graph

Abstract

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_{\rm st}(G)$ is defined as the minimum cardinality of a strong dominating set. In this paper, we study the effects on $\gamma_{\rm st}(G)$ when $G$ is modified by operations on vertices and edges of $G$.

Keywords

• strong domination number
• strong dominating set
• vertex contraction