Certified Total Domination in Graphs.

Abstract

Let G = (V(G), E(G)) be a simple undirected graph. A total dominating set S\subseteq V(G) is certified if every vertex in S has either zero or at least two neighbors outside S. The minimum cardinality of such a set is the certified total domination number, denoted by \gamma_{\mathrm{cer}}^{t}(G). We establish its relationship with total domination, determine exact values for several graph classes, and characterize certified total dominating sets in graph joins.