Total 2-Rainbow Domination in Graphs

Huiqin Jiang and Yongsheng Rao
Additional contact information
Huiqin Jiang: Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China
Yongsheng Rao: Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China

Mathematics, 2022, vol. 10, issue 12, 1-13

Abstract: A total k-rainbow dominating function on a graph G = ( V , E ) is a function f : V ( G ) → 2 { 1 , 2 , … , k } such that (i) ∪ u ∈ N ( v ) f ( u ) = { 1 , 2 , … , k } for every vertex v with f ( v ) = ∅ , (ii) ∪ u ∈ N ( v ) f ( u ) ≠ ∅ for f ( v ) ≠ ∅ . The weight of a total 2-rainbow dominating function is denoted by ω ( f ) = ∑ v ∈ V ( G ) | f ( v ) | . The total k-rainbow domination number of G is the minimum weight of a total k-rainbow dominating function of G . The minimum total 2-rainbow domination problem (MT2RDP) is to find the total 2-rainbow domination number of the input graph. In this paper, we study the total 2-rainbow domination number of graphs. We prove that the MT2RDP is NP-complete for planar bipartite graphs, chordal bipartite graphs, undirected path graphs and split graphs. Then, a linear-time algorithm is proposed for computing the total k-rainbow domination number of trees. Finally, we study the difference in complexity between MT2RDP and the minimum 2-rainbow domination problem.

Keywords: total 2-rainbow domination; total 2-rainbow domination number; NP-complete; linear-time algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/12/2059/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/12/2059/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:12:p:2059-:d:838600

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().