Some Results on [1, k]-sets of Lexicographic Products of Graphs

Abstract

A subset $S\subseteq V$ in a graph $G=(V,E)$ is called a $[1,k]$-set, if for every vertex $v\in V\setminus S$, $1\le |N_G(v)\cap S|\le k$. The $[1,k]$-domination number of $G$, denoted by ${\gamma }_{[1,k]}(G)$ is the size of the smallest $[1,k]$-sets of $G$. A set $S^{\prime }\subseteq V(G)$ is called a total $[1,k]$-set, if for every vertex $v\in V$, $1\le |N_G(v)\cap S|\le k$. If a graph $G$ has at least one total $[1,k]$-set then the cardinality of the smallest such set is denoted by ${\gamma }_{t[1,k]}(G)$. We consider $[1,k]$-sets that are also independent. Note that not every graph has an independent $[1,k]$-set. For graphs having an independent $[1,k]$-set, we define $[1,k]$-independence numbers which is denoted by ${\gamma }_{i[1,k]}(G)$. In this paper, we investigate the existence of $[1,k]$-sets in lexicographic products $G\circ H$. Furthermore, we completely characterize graphs which their lexicographic product has at least one total $[1,k]$-set. Also, we determine ${\gamma }_{[1,k]}(G\circ H)$, ${\gamma }_{t[1,k]}(G\circ H)$ and ${\gamma }_{i[1,k]}(G\circ H)$. Finally, we show that finding smallest total $[1,k]$-set is $NP$-complete.

References in corpus (1)

• [1, 2]-sets and [1, 2]-total Sets in Trees with Algorithms