Super dominating sets in graphs

Abstract

Let $G=(V,E)$ be a graph. A subset $D$ of $V(G)$ is called a super dominating set if for every $v\in V(G)-D$ there exists an external private neighbour of $v$ with respect to $V(G)-D.$ The minimum cardinality of a super dominating set is called the super domination number of $G$ and is denoted by ${\gamma }_{sp}(G)$. In this paper some results on the super domination number are obtained. We prove that if $T$ is a tree with at least three vertices, then $\frac{n}{2}\le {\gamma }_{sp}(T)\le n-s,$ where $s$ is the number of support vertices in $T$ and we characterize the extremal trees.

7 pages, 4 references