Edge Weighting Functions on Semitotal Dominating Sets

Abstract

A set S of vertices in an isolate-free graph G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number is the minimum cardinality of a semitotal dominating set of G, and is bounded below by the domination number and bounded above by the total domination number, arguably the two most important domination parameters. The upper semitotal domination number, $\Gamma _{t2}(G)$, of G is the maximum cardinality of a minimal semitotal dominating set in G. If G is a connected graph with minimum degree $\delta \ge 1$ and of order $n \ge \delta + 2$, then we show that $\Gamma _{t2}(G) \le n - \delta$, and that this bound is sharp for every fixed $\delta \ge 1$. Using edge weighting functions on semitotal dominating sets we show that if we impose a regularity condition on a graph, then this upper bound on the upper semitotal domination number can be greatly improved. We prove that if G is a 2-regular graph on n vertices with no $K_3$-component, then $\Gamma _{t2}(G) \le \frac{4}{7}n$, with equality if and only if every component of G is a cycle of length congruent to zero modulo 7. For $k \ge 3$, we prove that if G is a k-regular graph on n vertices, then $\Gamma _{t2}(G) \le \frac{1}{2}n$, and we characterize the infinite families of graphs that achieve equality in this bound.