Protection of lexicographic product graphs (Q2062678): Difference between revisions

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.