More on the super domination number of graphs
Authors:
- Nima GhanbariNGNima Ghanbari
- Gerold JägerGJGerold Jäger
- Tuomo LehtiläTLTuomo Lehtilä
Preprint
Abstract
Let $G=(V,E)$ be a simple graph. A dominating set of $G$ is a subset $S\subseteq V$ such that every vertex in $ V \setminus S$ is adjacent to at least one vertex in $S$. A dominating set $S$ is called super dominating set of $G$, if for every vertex $u\in \bar{S}=V \setminus S$, there exists a $v\in S$ such that $N(v)\cap\bar{S}=\{u\}$. The cardinality of a minimal size super dominating set of $G$, is the super domination number of $G$. The problem of finding the super domination number of a graph is $\mathcal{NP}$-hard. In this paper, we continue the study of super domination number of graphs and present tight bounds for neighbourhood corona, $r$-gluing and Haj\'{o}s sum of two graphs. We present infinite families of graphs attaining all of our bounds. Finally, we give the exact number of the minimal size super dominating sets in some graph classes.