An algorithm to check the equality of total domination number and double of domination number in graphs

Authors: SELİM BAHADIR

Abstract: In graph theory, domination number and its variants such as total domination number are studied by many authors. Let the domination number and the total domination number of a graph $G$ without isolated vertices be $\gamma(G)$ and $\gamma_t(G)$, respectively. Based on the inequality $\gamma_t(G) \leq 2\gamma(G)$, we investigate the graphs satisfying the upper bound, that is, graphs $G$ with $\gamma_t(G) = 2\gamma(G)$. In this paper, we present some new properties of such graphs and provide an algorithm which can determine whether $\gamma_t(G) = 2\gamma(G)$ or not for a family of graphs not covered by the previous results in the literature.

Keywords: Domination number, total domination number

Full Text: PDF