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

Authors

  • Mohammad Reza Hooshmandasl Yazd University
  • Pouyeh Sharifani Yazd University

DOI:

https://doi.org/10.30495/jme.v13i0.799

Keywords:

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

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.

Author Biography

Pouyeh Sharifani, Yazd University

Department of Computer Science, PhD candidate.

Downloads

Additional Files

Published

2019-03-13

Issue

Section

Vol. 13, No. 3, (2019)