ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


A. Tepeh


Total domination in generalized prisms and a new domination invariant


Discussiones Mathematicae Graph Theory

Received: 2019-06-14, Revised: 2019-09-12, Accepted: 2019-09-18,


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 $\gamma_{krt}(G)$, it is shown that the problem of finding the total domination number of a generalized prism $G\, \Box \, K_k$ is equivalent to an optimization problem of assigning subsets of $\{1,2,\ldots,k\}$ to vertices of $G$. Various properties of the new domination invariant are presented, including, inter alia, that $\gamma_{krt}(G) = n$ for a nontrivial graph $G$ of order $n$ as soon as $k \geq 2\Delta(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.


domination, $k$-rainbow total domination, total domination