Total [1, k]-sets of lexicographic product graphs with characterization
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 \leq \vert N_G(v) \cap S \vert \leq 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'\subseteq V(G)$ is called a total $[1,k]$-set, if for every vertex $v \in V$, $1 \leq \vert N_G(v) \cap S \vert \leq k$.
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.
Finally, we show that finding smallest total $[1, k]$-set is an $NP$-complete problem.
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'\subseteq V(G)$ is called a total $[1,k]$-set, if for every vertex $v \in V$, $1 \leq \vert N_G(v) \cap S \vert \leq k$.
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.
Finally, we show that finding smallest total $[1, k]$-set is an $NP$-complete problem.
Keywords
Domination; Total Domination; $[1,k]$-set; Total $[1,k]$-set; Independent $[1,k]$-set; Lexicographic Products.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.