Semitotal domination in trees

zbMATH Open1401.05227arXiv1803.10486MaRDI QIDQ4560258FDOQ4560258

Authors: Zhuang Wei, Hao Guoliang 

Publication date: 10 December 2018

Abstract: In this paper, we study a parameter that is squeezed between arguably the two important domination parameters, namely the domination number, $gamma(G)$, and the total domination number, $gamm{a}_t(G)$. 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, $gamm{a}_{t2}(G)$, is the minimum cardinality of a semitotal dominating set of $G$. We observe that $gamma(G)leqgamm{a}_{t2}(G)leqgamm{a}_t(G)$. In this paper, we give a lower bound for the semitotal domination number of trees and we characterize the extremal trees. In addition, we characterize trees with equal domination and semitotal domination numbers.

Full work available at URL: https://arxiv.org/abs/1803.10486

Recommendations

• A note on the semitotal domination number of a tree.
• Semitotal domination in graphs
• Vertices contained in all or in no minimum semitotal dominating set of a tree
• Semitotal domination of some known trees
• Domination versus semipaired domination in trees

zbMATH Keywords

treedominationsemitotal domination

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (16)

• Semitotal domination in graphs: partition and algorithmic results
• 2-OUTER-INDEPENDENT SEMITOTAL DOMINATION IN GRAPHS
• ISOLATE SEMITOTAL DOMINATION IN GRAPHS
• Vertices contained in all or in no minimum semitotal dominating set of a tree
• Trees with unique minimum semitotal dominating sets
• A note on the semitotal domination number of a tree.
• Semitotal domination in graphs
• Semitotal domination number of some graph operations
• Entire semitotal-point domination in graphs
• Semitotal domination of some known trees
• A characterization relating domination, semitotal domination and total Roman domination in trees
• An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph
• The semitotal domination problem in block graphs
• On matching and semitotal domination in graphs
• Domination versus semipaired domination in trees
• Semitotal domination versus domination and total domination in trees

This page was built for publication: Semitotal domination in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4560258)