The k -Rainbow Domination Number of C n ? C m

Hong Gao, Kun Li and Yuansheng Yang
Additional contact information
Hong Gao: College of Science, Dalian Maritime University, Dalian 116026, China
Kun Li: College of Science, Dalian Maritime University, Dalian 116026, China
Yuansheng Yang: School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China

Mathematics, 2019, vol. 7, issue 12, 1-19

Abstract: Given a graph G and a set of k colors, assign an arbitrary subset of these colors to each vertex of G . If each vertex to which the empty set is assigned has all k colors in its neighborhood, then the assignment is called a k -rainbow dominating function ( k RDF) of G . The minimum sum of numbers of assigned colors over all vertices of G is called the k -rainbow domination number of graph G , denoted by γ r k ( G ) . In this paper, we focus on the study of the k -rainbow domination number of the Cartesian product of cycles, C n ? C m . For k ≥ 8 , based on the results of J. Amjadi et al. (2017), γ r k ( C n ? C m ) = m n . For ( 4 ≤ k ≤ 7 ) , we give a proof for the new lower bound of γ r 4 ( C n ? C 3 ) . We construct some novel and recursive k RDFs which are good enough and upon these functions we get sharp upper bounds of γ r k ( C n ? C m ) . Therefore, we obtain the following results: (1) γ r 4 ( C n ? C 3 ) = 2 n ; (2) γ r k ( C n ? C m ) = k m n 8 for n ≡ 0 ( mod 4 ) , m ≡ 0 ( mod 4 ) ( 4 ≤ k ≤ 7 ) ; (3) for n ? 0 ( mod 4 ) or m ? 0 ( mod 4 ) , m n 2 ≤ γ r 4 ( C n ? C m ) ≤ m n 2 + m + n 2 − 1 and k m n 8 ≤ γ r k ( C n ? C m ) ≤ k m n + n 8 + m for 5 ≤ k ≤ 7 . We also discuss Vizing’s conjecture on the k -rainbow domination number of C n ? C m .

Keywords: rainbow domination; k -rainbow domination; cartesian product graph; cycle (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/12/1153/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/12/1153/ (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:7:y:2019:i:12:p:1153-:d:292774

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 ().