2020/01/06 by Wei Zhuang, Zhuang, Wei
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO
paper · pdf · doi:10.48550/arxiv.2001.01360
openalex publication_date 2020/01/06 · arxiv created 2020/05/25 · arxiv updated 2020/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set S of vertices in 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, γt2(G), is the minimum cardinality of a semitotal dominating set of G. The semitotal domination multisubdivision number of a graph G, msd_γt2(G), is the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the semitotal domination number of G. In this paper, we show that msd_γt2(G)≤ 3 for any graph G of order at least 3, we also determine the semitotal domination multisubdivision number for some classes of graphs and characterize trees T with msd_γt2(T)=3. On the other hand, we know that γt2(G) is a parameter that is squeezed between domination number, γ(G) and total domination number, γt(G), so for any tree T, we investigate the ratios \fracγt2(T)γ(T) and \fracγt(T)γt2(T), and present the constructive characterizations of the families of trees achieving the upper bounds.