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

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 γ(G) and γt(G), respectively. Based on the inequality γt(G) ≤ 2γ(G), we investigate the graphs satisfying the upper bound, that is, graphs G with γt(G) = 2γ(G). In this paper, we present some new properties of such graphs and provide an algorithm which can determine whether γt(G) = 2γ(G) or not for a family of graphs not covered by the previous results in the literature.