Total Domination in Generalized Prisms and a New Domination Invariant

In this paper we complement recent studies on the total domination of prisms by considering generalized prisms, i.e., Cartesian products of an arbitrary graph and a complete graph. By introducing a new domination invariant on a graph G, called the k-rainbow total domination number and denoted by γ_krt(G), it is shown that the problem of finding the total domination number of a generalized prism G □ K_k is equivalent to an optimization problem of assigning subsets of {1, 2, . . ., k} to vertices of G. Various properties of the new domination invariant are presented, including, inter alia, that γ_krt(G) = n for a nontrivial graph G of order n as soon as k ≥ 2Δ(G). To prove the mentioned result as well as the closed formulas for the k-rainbow total domination number of paths and cycles for every k, a new weight-redistribution method is introduced, which serves as an efficient tool for establishing a lower bound for a domination invariant.