Graphs with unique minimum semitotal dominating sets
Jie Chen, Shou‐Jun Xu · RAIRO - Operations Research · 2024
In an isolate-free graph G, a subset S of vertices 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 of G, denoted by γt2(G), is the minimum cardinality of a semitotal dominating set in G. We prove that if G is a connected graph with order n ⩾ 3 and a unique minimum semitotal dominating set, then γt2(G)≤(n−1)/2, and we characterize the infinite families of graphs that achieve equality in this bound. By strengthening the condition of the degree, we can get stronger upper bounds. Using edge weighting functions on semitotal dominating sets, for a connected graph G of order n with a unique minimum semitotal dominating set S, giving each edge in E[V (G) ∖ S, S] a weight of size within [0, 1], we prove that γt2(G)≤2/5n and this bound is sharp if the minimum degree of G is at least two, and γt2(G)≤1/3n if the minimum degree of G is at least three.