Closed formulas for the total Roman domination number of lexicographic product graphs

angleški

2021

letnik 20, številka 2

leksikografski produkt grafov   totalna dominacija   totalna rimljanska dominacija

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

Naj bo ?$G$? graf brez izoliranih vozlišč in ?$f\colon V(G) \to \{0, 1, 2\}$? funkcija. Naj bo ?V$V_i = \{x \in V(G) \colon f(x) = i\}$? za vsak ?$i \in \{0, 1, 2\}$?. Funkcija ?$f$? se imenuje totalna rimljanska dominacijska funkcija na ?$G$?, če je vsako vozlišče množice ?$V_0$? sosednje najmanj enemu vozlišču množice ?$V_2$? in če podgraf, induciran z ?$V_1 \cup V_2$?, nima nobenega izoliranega vozlišča. Teža funkcije ?$f$? je ?$\omega (f)=\sum_{v \in V(G)}f(v)$?. Minimalno težo, ki jo lahko dosežejo totalno rimljansko dominacijske funkcije na ?$G$?, imenujemo totalno rimljansko dominacijsko število grafa ?$G$? in označimo z ?$\gamma_{tR}(G)$?. Znano je, da je splošni problem izračuna ?$\gamma_{tR}(G)$? NP-težek. V članku pokažemo, da če je ?$G$? graf, ki nima nobenega izoliranega vozlišča, ?$H$? pa je netrivialen graf, potem je totalno rimljansko dominacijsko število leksikografskega produkta grafov ?$G \circ H$? podano z izrazom ?$$\gamma_{tR}(G)(G \circ H) = \begin{cases} 2 \gamma_{tR}(G) & \text{if} \; \gamma(H) \ge 2, \\ \xi(G) & \text{if} \; \gamma(H)=1,\end{cases}$$? kjer je ?$\gamma(H)$? dominacijsko število grafa ?$H$?, ?$\gamma_{t}(G)$? je totalno dominacijsko število grafa ?$G$?, ?$\xi (G)$? pa je dominacijski parameter, ki je definiran na grafu ?$G$?.

22.11.2022