pith. sign in

arxiv: 1210.0514 · v2 · pith:4EXAGH5Snew · submitted 2012-10-01 · 🧮 math.CO

Rainbow domination in the lexicographic product of graphs

classification 🧮 math.CO
keywords dominationnumberrainbowfunctionk-rainbowproductdominatinglexicographic
0
0 comments X
read the original abstract

Let k be a positive integer and let f be a map from V(G) to the set of all subsets of {1,2,3,...,k}. The function f is called a k-rainbow dominating function of G provided that whenever u is a vertex of G such that f(u) is the empty set, then for each integer r in {1,2,3,...,k} there is a neighbor x of u such that f(x) contains r. The k-rainbow domination number of G is the minimum sum (over all the vertices of G) of the cardinalities of the subsets assigned by a k-rainbow dominating function of G. The k-rainbow domination number of G is the ordinary domination number of the Cartesian product of G and a complete graph of order k. 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 the 2-rainbow domination number of the lexicographic product of G with H in terms of domination invariants of G, except for the case when H has 2-rainbow domination number 3 and there is a minimum 2-rainbow dominating function of H such that some vertex in H is assigned the label {1,2}.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.