From Italian domination in lexicographic product graphs to w-domination in graphs

angleški

2022

letnik 22, številka 1

italijanska dominacija   k-dominacija   k-kratna dominacija   leksikografski produkt grafov   w-dominacija

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

V članku pokažemo, da je mogoče indeks italijanske dominacije vsakega leksikografskega produkta grafov ?$G \circ H$? izraziti s pomočjo petih različnih dominacijskih parametrov grafa ?$G$?. Te parametre se da definirati z naslednjim poenotenim pristopom, ki zajema definicijo več dobro znanih dominacijskih parametrov, vpelje pa tudi nove. Naj ?$N(v)$? označuje odprto okolico vozlišča ?$v \in V(G)$? in naj bo ?$w = (w_0, w_1, \dots, w_l)$? vektor nenegativnih celih števil, pri čemer je ?$w_0 \geq 1$?. Pravimo, da je funkcija ?$f: V(G) \rightarrow \{0, 1, \dots, l\}$? ?$w$?- ominirajoča, če je ?$f(N(v)) = f(N(v)) = \sum_{u \in N(v)}f(u) \geq w_i$? za vsako vozlišče ?$v$?, za katero je ?$f(v) = i$.? Teža funkcije ?$f$? je definirana kot ?$\omega (f) = \sum_{v \in V(G)}f(v)$?, ?$w$?-dominacijski indeks grafa ?$G$?, označen z ?$\gamma_w(G)$?, pa je minimalna teža vseh ?$w$?-dominacijskih funkcij na grafu ?$G$?. Pokažemo, da je ?$\gamma_I(G \circ H) = \gamma_w(G)$?, kjer je ?$w\in{2} \times \{0, 1, 2\}^l$? in ?$l\in \{2, 3\}$?. Če takšna enakost velja za specifične vrednosti ?$w_0, \dots, w_l$?, je odvisno od vrednosti dominacijskega indeksa grafa ?$H$?. Ta članek prinaša preliminarne rezultate v zvezi z ?$\gamma_w(G)$? in zastavlja izziv za podroben študij te teme.

22.11.2022