Total domination in graphs

Abstract

Abstract A set D of vertices of a finite, undirected graph G = ( V, E ) is a total dominating set if every vertex of V is adjacent to some vertex of D . In this paper we initiate the study of total dominating sets in graphs and, in particular, obtain results concerning the total domination number of G (the smallest number of vertices in a total dominating set) and the total domatic number of G (the largest order of a partition of G into total dominating sets).