Properties of the Global Total <i>k</i>-Domination Number

Abstract

A nonempty subset D⊂V of vertices of a graph G=(V,E) is a dominating set if every vertex of this graph is adjacent to at least one vertex from this set except the vertices which belong to this set itself. D⊆V is a total k-dominating set if there are at least k vertices in set D adjacent to every vertex v∈V, and it is a global total k-dominating set if D is a total k-dominating set of both G and G¯. The global total k-domination number of G, denoted by γktg(G), is the minimum cardinality of a global total k-dominating set of G, GTkD-set. Here we derive upper and lower bounds of γktg(G), and develop a method that generates a GTkD-set from a GT(k−1)D-set for the successively increasing values of k. Based on this method, we establish a relationship between γ(k−1)tg(G) and γktg(G), which, in turn, provides another upper bound on γktg(G).

Keywords

• global total domination
• total <i>k</i>-domination number