Loading [MathJax]/jax/output/HTML-CSS/jax.js
Digital repository of Slovenian research organisations

Show document
A+ | A- | Help | SLO | ENG

Title:Complexity of 2-rainbow total domination problem
Authors:ID Kraner Šumenjak, Tadeja (Author)
ID Tepeh, Aleksandra (Author)
Files:.pdf PDF - Presentation file, download (391,20 KB)
MD5: 22D44F33D85AFC2D4B25C054EC78E837
 
URL URL - Source URL, visit https://link.springer.com/article/10.1007/s40840-024-01747-8
 
Language:English
Typology:1.01 - Original Scientific Article
Organization:Logo IMFM - Institute of Mathematics, Physics, and Mechanics
Abstract: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.
Keywords:domination, rainbow domination, rooted product, NP-complete
Publication status:Published
Publication version:Version of Record
Publication date:01.09.2024
Year of publishing:2024
Number of pages:12 str.
Numbering:Vol. 47, iss. 5, article no. 155
PID:20.500.12556/DiRROS-20226 New window
UDC:519.17
ISSN on article:0126-6705
DOI:10.1007/s40840-024-01747-8 New window
COBISS.SI-ID:204512515 New window
Note:
Publication date in DiRROS:26.08.2024
Views:430
Downloads:224
Metadata:XML DC-XML DC-RDF
:
KRANER ŠUMENJAK, Tadeja and TEPEH, Aleksandra, 2024, Complexity of 2-rainbow total domination problem. Bulletin of the Malaysian Mathematical Sciences Society [online]. 2024. Vol. 47, no. 5,  155. [Accessed 7 April 2025]. DOI 10.1007/s40840-024-01747-8. Retrieved from: https://dirros.openscience.si/IzpisGradiva.php?lang=eng&id=20226
Copy citation
  
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Bulletin of the Malaysian Mathematical Sciences Society
Shortened title:Bull. Malays. Math. Sci. Soc.
Publisher:Springer Nature, Malaysian Mathematical Society.
ISSN:0126-6705
COBISS.SI-ID:515781657 New window

Document is financed by a project

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P1-0297
Name:Teorija grafov
Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P1-0383
Name:Kompleksna omrežja

Licences

License:CC BY 4.0, Creative Commons Attribution 4.0 International
Link:http://creativecommons.org/licenses/by/4.0/
Description:This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

Language:Slovenian
Keywords:dominacija, mavrična dominacija, matematika


Back