Rainbow domination in the lexicographic product of graphs
| Autor: | Sumenjak, Tadeja Kraner, Rall, Douglas F., Tepeh, Aleksandra |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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}. Comment: 14 pages, 2 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|