Weak total domination in graphs

Abstract

A set D of vertices in a graph G = (V, E) is a total dominating set if every vertex of G is adjacent to some vertex in D. A total dominating set D of G is said to be weak if every vertex ν ∈ V - D is adjacent to a vertex u ∈ D such that d_G(v) > d_G(u). The weak total domination number γ_wt(G) of G is the minimum cardinality of a weak total dominating set of G. In this paper we initiate the study of weak total domination in graphs. We present lower and upper bounds on γ_wt(G) with some characterizations, and we show that determining the number γ_wt(G) for an arbitrary graph is NP- complete. Then we provide a constructive characterization of trees with equal weak total domination and total domination numbers.