A Characterization of Trees with Equal Domination and Total Domination Numbers

Abstract

Let \(G = (V,E)\) be a graph. A set \(S \subseteq V\) is a dominating set of \(G\) if every vertex not in \(S\) is adjacent to some vertex in \(S\). The domination number of \(G\), denoted by \(\gamma(G)\), is the minimum cardinality of a dominating set of \(G\). A set \(S \subseteq V\) is a total dominating set of \(G\) if every vertex of \(V\) is adjacent to some vertex in \(S\). The total domination number of \(G\), denoted by \(\gamma_t(G)\), is the minimum cardinality of a total dominating set of \(G\). In this paper, we provide a constructive characterization of those trees with equal domination and total domination numbers.