$k$-Domination Stable Graphs upon Edge Removal

Abstract

Let $k$ be a positive integer and $G=(V(G),E(G))$ a graph. A subset $S\subseteq V(G)$ is a $k$-dominating set if every vertex of $V(G)-S$ is adjacent to at least $k$ vertices of $S$. The $k$-domination number ${\gamma }_k(G)$ is the minimum cardinality of a $k$-dominating set of $G$. A graph $G$ is called ${\gamma }_k$-stable if ${\gamma }_{\overline{k}}(G–e)={\gamma }_k(G)$ for every edge $e$ of $E(G)$. We first provide a necessary and sufficient condition for ${\gamma }_{\overline{k}}$-stable graphs. Then, for $k\ge 2$, we offer a constructive characterization of ${\gamma }_{\overline{k}}$-stable trees.