On Trees with Double Domination Number Equal to Total Domination Number Plus One

Marcin Krzywkowski1
1Faculty of Applied Physics and Mathematics Gdarisk University of Technology Narutowicza 11/12, 80-233 Gdarisk, Poland

Abstract

A total dominating set of a graph \(G\) is a set \(D\) of vertices of \(G\) such that every vertex of \(G\) has a neighbor in \(D\). A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph \(G\) is a set \(D\) of vertices of \(G\) such that every vertex of \(G\) is dominated by at least two vertices of \(D\). The total (double, respectively) domination number of a graph \(G\) is the minimum cardinality of a total (double, respectively) dominating set of \(G\). We characterize all trees with double domination number equal to total domination number plus one.