Total Domination in Generalized Prisms and a New Domination Invariant

Abstract

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 □ Kk 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.

Keywords

• domination
• k-rainbow total domination
• total domination
• 05c69
• 05c76