Domination stability in graphs

Marcin Krzywkowski
University of Johannesburg



Content: A subset $D$ of the set of vertices of a graph $G$ is a dominating set if any vertex not in $D$ is adjacent to some vertex of $D$. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set of $G$. The concept of domination stability was introduced in [1]. The domination stability, or just $\gamma$-stability of a graph $G$ is the minimum number of vertices whose removal changes the domination number. We show that the decision problem for domination stability is NP-complete even when restricted to bipartite graphs, and we determine domination stability for several classes of graphs. We present several sharp bounds for the domination stability and we characterize graphs achieving equality of the bounds. In particular, we characterize all trees with domination stability $1$ or $2$. We also consider this concept for several domination parameters. This is a joint work with Nader Jafari Rad and Elahe Sharifi. \medskip \noindent{\bf Keywords:} domination, domination stability \vspace{5mm} \noindent{\bf References:} \begin{itemize} \item[{[1]}] D. Bauer, F. Harary, J. Nieminen and C. Suffel, {\it Domination alternation sets in graphs,} Discrete Mathematics 47 (1983), 153--161. \end{itemize}

Back to all abstracts