Rainbow domination in the lexicographic product of graphs
Abstrak
A k-rainbow dominating function of a graph G is a map f from V(G) to the set of all subsets of {1,2,...,k} such that {1,...,k}[email protected]?"u"@?"N"("v")f(u) whenever v is a vertex with f(v)[email protected]?. The k-rainbow domination number of G is the invariant @c"r"k(G), which is the minimum sum (over all the vertices of G) of the cardinalities of the subsets assigned by a k-rainbow dominating function. We focus on the 2-rainbow domination number of the lexicographic product of graphs and prove sharp lower and upper bounds for this number. In fact, we prove the exact value of @c"r"2([email protected]?H) in terms of domination invariants of G except for the case when @c"r"2(H)=3 and there exists a minimum 2-rainbow dominating function of H such that there is a vertex in H with the label {1,2}.
Topik & Kata Kunci
Penulis (3)
T. K. Sumenjak
Douglas F. Rall
Aleksandra Tepeh
Akses Cepat
- Tahun Terbit
- 2012
- Bahasa
- en
- Total Sitasi
- 43×
- Sumber Database
- Semantic Scholar
- DOI
- 10.1016/j.dam.2013.03.011
- Akses
- Open Access ✓