Total [1, k]-sets of lexicographic product graphs with characterization

Mohammad Reza Hooshmandasl, Pouyeh Sharifani

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.

Keywords


Domination; Total Domination; $[1,k]$-set; Total $[1,k]$-set; Independent $[1,k]$-set; Lexicographic Products.

Full Text: PDF

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.