Menu
Let \(G = (V, E)\) be a graph. A vertex \(u\) strongly dominates a vertex \(v\) if \(uv \in E\) and \(\deg(u) > \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) \leq \frac{4p – 1}{7}\)
and this bound is sharp.
For any connected graph \(G\) of order \(p \geq 3\), it is shown that \(\gamma_{st}(G) \leq \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.