Protection of lexicographic product graphs
type: Item
instance of: scholarly article
title: Protection of lexicographic product graphs
zbMATH Open document ID: 1482.05254
publication date: 2022-01-03T00:00:00Z
review text: Let \(G\) be a graph. A map \(f:V(G)\rightarrow\{0,1,2\}\) can be presented by a partition \((V_0,V_1,V_2)\) of \(V(G)\) where \(v\in V_i\) if \(f(v)=i\) for \(i\in \{0,1,2\}\). A vertex \(v\) of \(G\) is defended by \(f\) if \(N_G[v]\cap (V_1\cup V_2)\neq \emptyset\) where \(N_G[v]\) is the closed neighborhood of \(v\). Now, \(f\) is called a weak Roman domination function if for every \(u\in V_0\) there exists its neighbor \(v\in V_1\cup V_2\), such that every vertex of \(G\) is defended by a new function \(f^\prime:V(G)\rightarrow\{0,1,2\}\) defined by \(f^\prime(u)=1\), \(f^\prime(v)=f(v)-1\) and \(f^\prime(z)=f(z)\) for every \(z\in V(G)-\{u,v\}\). The weight of a weak Roman domination function is \(w(f)=|V_1|+2|V_2|\). The weak Roman domination number \(\gamma_r(G)\) is the minimum weight \(w(f)\) over all weak Roman domination functions \(f\). A set \(D\subseteq V(G)\) is a dominating set if every vertex \(v\in V(G)-D\) is adjacent to a vertex \(u\in D\). A dominating set \(S\) is secured dominating set if for every vertex \(v\in V(G)-D\) there exists a neighbor \(u\in S\) of \(v\) such that \((S-\{u\})\cup\{v\}\) is a dominating set of \(G\). The secure dominating number \(\gamma_s(G)\) of \(G\) is the minimum cardinality of a secure dominating set of \(G\). The lexicographic product \(G\circ H\) of graphs \(G\) and \(H\) is a graph with \(V(G\circ H)=V(G)\times V(H)\). Two vertices \((g,h)\) and \((g^\prime,h^\prime)\) are adjacent in \(G\circ H\) if \(gg^\prime\in E(G)\) or (\(g=g^\prime\) and \(hh'\in E(H)\)). The authors first show the equality \(\gamma_r(G\circ H)=\gamma_s(G\circ H)\) for a graph \(G\) without isolated vertices and any graph \(H\) with \(\gamma_s(H)\leq 2\) or \(\gamma_r(H)\geq 3\). Later, they underline the mentioned equality with several exact results where the first graph \(G\) is a complete graph or a path or a cycle and the second graph \(H\) is arbitrary.
reviewed by: Iztok Peterin
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C76
zbMATH DE Number: 7451245
zbMATH Keywords: weak Roman domination number
zbMATH Keywords: secure domination number
zbMATH Keywords: lexicographic product
author: Douglas J. Klein
author: Juan A. Rodríguez-Velázquez
MaRDI profile type: Publication
full work available at URL: dmgt.2243
OpenAlex ID: W2981008656
cites work: Graph-theoretic parameters concerning domination, independence, and irredundance
cites work: On secure domination in graphs
cites work: Vertex Covers and Secure Domination in Graphs
cites work: Bounds on weak Roman and 2-rainbow domination numbers
cites work: Total domination in graphs
cites work: Q4812925
cites work: Q5461685
cites work: Roman domination in graphs.
cites work: On the super domination number of lexicographic product graphs
cites work: Domination in planar graphs with small diameter*
cites work: Q3005852
cites work: Q4368729
cites work: Q4368728
cites work: Defending the Roman Empire---a new strategy
cites work: Total Domination in Graphs
cites work: Q4523707
cites work: Secure domination and secure total domination in graphs
cites work: Domination in lexicographic product digraphs.
cites work: Associative graph products and their independence, domination and coloring numbers
cites work: On the roman domination in the lexicographic product of graphs
cites work: Rainbow domination in the lexicographic product of graphs
cites work: On the weak Roman domination number of lexicographic product graphs
cites work: Protection of graphs with emphasis on Cartesian product graphs
Wikidata QID: Q127010765
DOI: 10.7151/DMGT.2243
published in: Discussiones Mathematicae Graph Theory
description: scientific article; zbMATH DE number 7451245