Graphs with unique minimum semitotal dominating sets

School of Mathematics and Statistics, Gansu Center for Applied Mathematics, Lanzhou University, Lanzhou, Gansu 730000, P.R. China

^* Corresponding author: shjxu@lzu.edu.cn

Received: 17 April 2024
Accepted: 29 December 2024

Abstract

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.