\([1,k]\)-domination number of lexicographic products of graphs (Q2227955)

Let \(G = (V, E)\) be a graph. Let \(k\) be a positive integer. A subset \(D\) of vertices of a graph \(G\) is \([1, k]\)-dominating if every vertex not in \(D\) can have at least one neighbor in \(D\) and at most \(k\) neighbors in \(D\). \(\gamma_{[1,k]}(G)\) denotes the cardinality of a smallest \([1, k]\)-dominating set. A \([1, k]\)-dominating set of cardinality \(\gamma_{[1,k]}(G)\) is called \(\gamma_{[1,k]}(G)\)-set. A \([1, k]\)-total dominating set of \(G\), is a set \(D\) of vertices such that every vertex in \(G\) is adjacent to at least \(1\) and at most \(k\) vertices in \(D\). By \(\gamma_{t[1,k]}(G)\) is the cardinality of a smallest \([1, k]\)-total dominating set (if there exists one) and is \(\infty\) if no \([1, k]\)-total dominating set exists. A set \(S \subseteq V(G)\) is \(k\)-independent in \(G\) if \(\Delta(G[S]) < k\). The \(k\)-independence number of \(G\) is the maximum cardinality of a \(k\)-independent set of \(G\). We denote the \(k\)-independence number by \(\alpha_k (G)\) and call a \(k\)-independent set of cardinality \(\alpha_k (G)\) as an \(\alpha_k (G)\)-set. The minimum cardinality of a \([1, k]\)-total dominating \(k\)-independent set, if it exists, is denoted by \(\gamma^{\alpha_k}_{t[1,k]}(G)\). The lexicographic product of graphs \(G\) and \(H\), denoted by \(G\circ H\), is a graph with the vertex set \(V(G\circ H) = V(G) \times V(H)\), where two vertices \((g, h)\) and \((g^\prime, h^\prime)\) are adjacent in \(G\circ H\) if either \(gg'\in E(G)\) or \(g = g^\prime\) and \(hh^\prime\in E(H)\). Let \(C_1,\dots ,C_k\) be the connected components of a graph \(H\). By \(c(H)\), we denote the smallest cardinality of vertices in a component of \(H\). For an arbitrary dominating set \(D\), authors partitioned \(D\) into sets \(D_1 = \{v \in D: d_{G[D]}(v) = 0\}\), \(D_2 =\{v \in D: d_{G[D]}(v) > k\}\), \(D_3 = \{v \in D: 1\le d_{G[D]}(v)< k\}\) and \(D_4 = \{v \in D: d_{G[D]}(v) = k\}\). The main results are: 1. Let \(G\) be a connected graph, \(H\) a graph and \(k \ge 2\) be an integer. If \(\gamma_{[1,k]}( H)> k\) and \(c(H)=1\), then \[\gamma_{[1,k]}(G\circ H)=\left\{ \begin{array}{ll} \gamma_{t[1,k]}(G) & \hbox{if}\ \gamma_{t[1,k]}(G)<\infty, \\ |V(G)||V(H)| & \hbox{otherwise.} \end{array} \right.\] 2. Let \(G\) be a connected graph, \(H\) a graph and \(k \ge 2\) be an integer. If \(\gamma_{[1,k]}( H)> k\) and \(c(H)\ge k\), then \[\gamma_{[1,k]}(G\circ H)=\left\{ \begin{array}{ll} \gamma^{\alpha_k}_{t[1,k]}(G) & \hbox{if}\ \gamma^{\alpha_k}_{t[1,k]}(G)<\infty, \\ |V(G)||V(H)| & \hbox{otherwise.} \end{array} \right.\] 3. Let \(G\) be a connected graph, \(H\) a graph and \(k \ge 2\) be an integer. If \(\gamma_{[1,k]}( H)=1\) and \(c(H)> k\), then \[\gamma_{[1,k]}(G\circ H)=\left\{ \begin{array}{ll} \gamma^{\alpha_k}_{t[1,k]}(G) & \hbox{if}\ \gamma^{\alpha_k}_{t[1,k]}(G)<\infty, \\ |V(G)||V(H)| & \hbox{otherwise.} \end{array} \right.\] 4. Let \(G\) be a connected graph, \(H\) a graph and \(k \ge 2\) be an integer. If \(\gamma_{[1,k]}( H)> k\) and \(c(H)\ge k\), then \(\gamma_{[1,k]}(G\circ H)=\min_{D\in \mathcal{D}_1(G)} \{|D_1|\gamma_{[1,k]}( H)+|D_2||V(H)|+|D_3|\}\). 5. Let \(G\) be a connected graph, \(H\) a graph of order at least \(2\), and \(k \ge 2\) be an integer. If \(\gamma_{[1,k]}( H)=1\) and \(|V(H)|\le k\), then \(\gamma_{[1,k]}(G\circ H)=\min_{D\in \mathcal{D}_1(G)} \{|D_1|+|D_2||V(H)|+|D_3|\}\). 6. Let \(G\) be a connected graph, \(H\) a graph and \(k\) be a positive integer. If \(\gamma_{[1,k]}( H)> k\) and \(2\le c(H)< k\), then \[\gamma_{[1,k]}(G\circ H)=\left\{ \begin{array}{ll} \min_{D\in \mathcal{D}_2(G)} \{|D_3|+|D_4|c(H)\} & \mathcal{D}_2(G)\ne \emptyset, \\ |V(G)||V(H)| & \hbox{otherwise.} \end{array} \right.\]