Complexity of 2-rainbow total domination problem

Kraner Šumenjak, Tadeja; Tepeh, Aleksandra

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Complexity of 2-rainbow total domination problem
Authors:	ID Kraner Šumenjak, Tadeja (Author) ID Tepeh, Aleksandra (Author)
Files:	s40840-024-01747-8.pdf (390,07 KB) MD5: 8641E18DFB971561E13E80F6DF8C5646 https://link.springer.com/article/10.1007/s40840-024-01747-8
Language:	English
Work type:	Article
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
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
Submitted for review:	05.02.2024
Article acceptance date:	11.07.2024
Publication date:	08.08.2024
Publisher:	Springer Link
Year of publishing:	2024
Number of pages:	12 str.
PID:	20.500.12556/DKUM-89967
UDC:	51
ISSN on article:	2180-4206
COBISS.SI-ID:	204512515
DOI:	10.1007/s40840-024-01747-8
Copyright:	© The Author(s) 2024
Publication date in DKUM:	20.08.2024
Views:	203
Downloads:	31
Metadata:
Categories:	Misc.
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
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
Publisher:	Universiti Sains Malaysia
ISSN:	2180-4206
COBISS.SI-ID:	512695613

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

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back