20.500.12556/DKUM-51430 Rainbow domination in the lexicographic product of graphs Mavrična dominacija v leksikografskem produktu grafov Preslikava iz množice vozlišč grafa ▫$G$▫ v potenčno množico množice ▫${1,2,dots, k}$▫ se imenuje ▫$k$▫-mavrična dominantna funkcija, če za poljubno vozlišče ▫$v$▫ z lastnostjo ▫$f(v) = emptyset$▫ velja ▫${1,dots,k} = bigcup_{u in N(v)}f(u)$▫. Obravnavamo ▫$k$▫-mavrično dominantno število grafa ▫$G$▫, ▫$gamma_{rk}(G)$▫, ki je minimalna vsota (po vseh vozliščih grafa ▫$G$▫) moči podmnožic, ki so vozliščem dodeljena s ▫$k$▫-mavrično dominantno funkcijo. V članku se osredotočimo na 2-mavrično dominantno število leksikografskega produkta grafov in dokažemo natančno spodnjo in zgornjo mejo za to število. Dejansko pokažemo natančno vrednost za ▫$gamma_{r2}(G circ H)$▫, razen v primeru, ko je ▫$gamma_{r2}(H) = 3$▫ in obstaja taka minimalna 2-mavrična dominantna funkcija grafa $H$, ki nekemu vozlišču v grafu ▫$H$▫ dodeli oznako ▫${1,2}$▫. 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,dots,k}$▫ such that ▫${1,dots,k} = bigcup_{u in N(v)}f(u)$▫ whenever ▫$v$▫ is a vertex with ▫$f(v) = emptyset$▫. The ▫$k$▫-rainbow domination number of ▫$G$▫ is the invariant ▫$gamma_{rk}(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 ▫$gamma_{r2}(G circ H)$▫ in terms of domination invariants of ▫$G$▫ except for the case when ▫$gamma_{r2}(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}$▫. dominacija popolna dominacija mavrična dominacija leksikografski produkt domination total domination rainbow domination lexicographic product true false false Angleški jezik Angleški jezik Delo ni kategorizirano 2015-07-10 14:46:20 2015-07-10 14:46:20 2022-05-30 03:05:48 2019-07-11 07:18:47 2013 0 0 str. 2133-2141 iss. 13-14 Vol. 161 2013 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 25342464 3514668 0166-218X URN:SI:UM:DK:T5MCBN6Z http://dx.doi.org/10.1016/j.dam.2013.03.011 1 https://dk.um.si/Dokument.php?lang=slv&id=75990 Fakulteta za kmetijstvo in biosistemske vede 0 0 0