20.500.12556/DKUM-89967 Complexity of 2-rainbow total domination problem In this paper, we extend the findings of recent studies on k-rainbow total domination by placing our focus on its computational complexity aspects. We show that the problem of determining whether a graph has a 2-rainbow total dominating function of a given weight is NP-complete. This complexity result holds even when restricted to planar graphs. Along the way tight bounds for the k-rainbow total domination number of rooted product graphs are established. In addition, we obtain the closed formula for the k-rainbow total domination number of the corona product G ∗ H, provided that H has enough vertices. domination rainbow domination rooted product NP-complete dominacija mavrična dominacija matematika true false true Springer Link Angleški jezik Slovenski jezik https://link.springer.com/journal/40840 © The Author(s) 2024 Članek v reviji 2024-08-20 10:13:35 2024-08-20 10:13:35 2026-01-31 03:16:01 0000-00-00 00:00:00 2024 0 0 12 str. Published 08 August 2024 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2024-02-05 2024-07-11 2024-08-08 51 204512515 10.1007/s40840-024-01747-8 2180-4206 s40840-024-01747-8.pdf s40840-024-01747-8.pdf 1 8641E18DFB971561E13E80F6DF8C5646 016136ee2982ee338e235248653b80fc586416042fc2755de86292335ead9116 a10af12a-fdba-11f0-8805-00155d00018d https://dk.um.si/Dokument.php?lang=slv&id=202833 https://link.springer.com/article/10.1007/s40840-024-01747-8 0 a8abd728-fdba-11f0-8805-00155d00018d https://dk.um.si/Dokument.php?lang=slv&id=202834 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0