Zhuang Wei ; Hao Guoliang - Semitotal domination in trees

dmtcs:4413 - Discrete Mathematics & Theoretical Computer Science, September 28, 2018, vol. 20 no. 2 - https://doi.org/10.23638/DMTCS-20-2-5
Semitotal domination in treesArticle

Authors: Zhuang Wei ; Hao Guoliang

    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, $\gamma_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, $\gamma_{t2}(G)$, is the minimum cardinality of a semitotal dominating set of $G$. We observe that $\gamma(G)\leq \gamma_{t2}(G)\leq \gamma_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.


    Volume: vol. 20 no. 2
    Section: Graph Theory
    Published on: September 28, 2018
    Accepted on: September 13, 2018
    Submitted on: March 29, 2018
    Keywords: Mathematics - Combinatorics

    1 Document citing this article

    Consultation statistics

    This page has been seen 673 times.
    This article's PDF has been downloaded 458 times.