311 KB22 KB200820252021Cabrera Martinez, AbelRodríguez-Velázquez, Juan Albertoštevilka:2letnik:20str. 233-241DOI:10.26493/1855-3974.2284.aebISSN:1855-3966COBISSID_HOST:92559619URN:URN:NBN:SI:doc-19AVH494enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporanealeksikografski produkt grafovlexicographic product graphtotal dominationtotal Roman dominationtotalna dominacijatotalna rimljanska dominacijaClosed formulas for the total Roman domination number of lexicographic product graphs|Let ?$G$? be a graph with no isolated vertex and ?$f\colon V(G) \to \{0, 1, 2\}$? a function. Let ?$V_i = \{x \in V(G) \colon f(x) = i\}$? for every ?$i \in \{0, 1, 2\}$?. We say that ?$f$? is a total Roman dominating function on ?$G$? if every vertex in ?$V_0$? is adjacent to at least one vertex in ?$V_2$? and the subgraph induced by ?$V_1 \cup V_2$? has no isolated vertex. The weight of ?$f$? is ?$\omega (f)=\sum_{v \in V(G)}f(v)$?. The minimum weight among all total Roman dominating functions on ?$G$? is the total Roman domination number of ?$G$?, denoted by $\gamma_{tR}(G)$. It is known that the general problem of computing $\gamma_{tR}(G)$ is NP-hard. In this paper, we show that if ?$G$? is a graph with no isolated vertex and ?$H$? is a nontrivial graph, then the total Roman domination number of the lexicographic product graph ?$G \circ H$? is given by ?$$\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}$$? where ?$\gamma(H)$? is the domination number of ?$H$?, ?$\gamma_{t}(G)$? is the total domination number of ?$G$? and ?$\xi (G)$? is a domination parameter defined on ?$G$?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$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije