More on the super domination number of graphs

Authors:
  • NGNima Ghanbari
    Nima Ghanbari
  • GJGerold Jäger
    Gerold Jäger
  • TLTuomo Lehtilä
    Tuomo Lehtilä

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.