Edge Weighting Functions on Semitotal Dominating Sets

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)


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, Γ t 2(G) , of G is the maximum cardinality of a minimal semitotal dominating set in G. If G is a connected graph with minimum degree δ≥ 1 and of order n≥ δ+ 2 , then we show that Γ t 2(G) ≤ n- δ, and that this bound is sharp for every fixed δ≥ 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 K3-component, then Γt2(G)≤47n, with equality if and only if every component of G is a cycle of length congruent to zero modulo 7. For k≥ 3 , we prove that if G is a k-regular graph on n vertices, then Γt2(G)≤12n, and we characterize the infinite families of graphs that achieve equality in this bound.

Original languageEnglish
Pages (from-to)403-417
Number of pages15
JournalGraphs and Combinatorics
Issue number2
Publication statusPublished - 1 Mar 2017


  • Regular graphs
  • Upper semitotal domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Edge Weighting Functions on Semitotal Dominating Sets'. Together they form a unique fingerprint.

Cite this