Back to Search
Start Over
Total 2-Rainbow Domination in Graphs.
- Source :
-
Mathematics (2227-7390) . Jun2022, Vol. 10 Issue 12, p2059-N.PAG. 13p. - Publication Year :
- 2022
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *DOMINATING set
*BIPARTITE graphs
*PLANAR graphs
*UNDIRECTED graphs
Subjects
Details
- Language :
- English
- ISSN :
- 22277390
- Volume :
- 10
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- Mathematics (2227-7390)
- Publication Type :
- Academic Journal
- Accession number :
- 157795608
- Full Text :
- https://doi.org/10.3390/math10122059