Povzetek
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\}$▫.
Ključne besede
dominacija;popolna dominacija;mavrična dominacija;leksikografski produkt;domination;total domination;rainbow domination;lexicographic product;
Podatki
Jezik: |
Angleški jezik |
Leto izida: |
2013 |
Tipologija: |
1.01 - Izvirni znanstveni članek |
Organizacija: |
UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko |
UDK: |
519.17 |
COBISS: |
3514668
|
ISSN: |
0166-218X |
Št. ogledov: |
883 |
Št. prenosov: |
101 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Angleški jezik |
Sekundarni naslov: |
Mavrična dominacija v leksikografskem produktu grafov |
Sekundarni povzetek: |
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\}$▫. |
URN: |
URN:SI:UM: |
Vrsta dela (COBISS): |
Delo ni kategorizirano |
Strani: |
str. 2133-2141 |
Letnik: |
ǂVol. ǂ161 |
Zvezek: |
ǂiss. ǂ13-14 |
Čas izdaje: |
2013 |
ID: |
1471833 |