LAUSR.org creates dashboard-style pages of related content for over 1.5 million academic articles. Sign Up to like articles & get recommendations!

Edge Weighting Functions on Semitotal Dominating Sets

Photo by dynamicwang from unsplash

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… Click to show full 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)$$Γ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$$δ≥1 and of order $$n \ge \delta + 2$$n≥δ+2, then we show that $$\Gamma _{t2}(G) \le n - \delta $$Γt2(G)≤n-δ, and that this bound is sharp for every fixed $$\delta \ge 1$$δ≥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$$K3-component, then $$\Gamma _{t2}(G) \le \frac{4}{7}n$$Γ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 \ge 3$$k≥3, we prove that if G is a k-regular graph on n vertices, then $$\Gamma _{t2}(G) \le \frac{1}{2}n$$Γt2(G)≤12n, and we characterize the infinite families of graphs that achieve equality in this bound.

Keywords: domination number; semitotal dominating; edge weighting; dominating set; domination

Journal Title: Graphs and Combinatorics
Year Published: 2017

Link to full text (if available)


Share on Social Media:                               Sign Up to like & get
recommendations!

Related content

More Information              News              Social Media              Video              Recommended



                Click one of the above tabs to view related content.