On Strong Domination in Graphs

Abstract

Let $G=(V,E)$ be a graph. A vertex $u$ strongly dominates a vertex $v$ if $uv\in E$ and $\mathrm{deg}(u)>\mathrm{deg}(v)$. A set $S\subseteq V$ is a strong dominating set of $G$ if every vertex in $V–S$ is strongly dominated by at least one vertex of $S$.

The minimum cardinality among all strong dominating sets of $G$ is called the strong domination number of $G$ and is denoted by ${\gamma }_{st}(G)$. This parameter was introduced by Sampathkumar and Pushpa Latha in [4].

In this paper, we investigate sharp upper bounds on the strong domination number for a tree and a connected graph. We show that for any tree $T$ of order $p>2$ that is different from the tree obtained from a star $K_{1,3}$ by subdividing each edge once,
${\gamma }_{st}(T)\le \frac{4p–1}{7}$
and this bound is sharp.

For any connected graph $G$ of order $p\ge 3$, it is shown that ${\gamma }_{st}(G)\le \frac{2(p–1)}{3}$ and this bound is sharp. We show that the decision problem corresponding to the computation of ${\gamma }_{st}$ is NP-complete, even for bipartite or chordal graphs.