Total [1, k]-Sets in the Lexicographic Product of Graphs.

A subset S Ç V in a graph G = (V, E) is called a [1, k]-set, if for every vertex v 6 V\S, 1 < |NG(v) nS| < k. The [1, k]-domination number of G, denoted by Y[i,k](G) is the size of the smallest [1,k]-sets of G. A set S' Ç V (G) is called a total [1,k]-set, if for every vertex v e v, 1 < |.ezG(v) ns| $\ k. If a {graph G has at least one total [1, k]-set then the cardinality of the smallest such setz is denoted by Yt[1,k](G). In this paper, we investigate the existence of [1,k]-sets in lexicographic products Go Ti. Furthermore, we completely characterize graphs whose lexicographic product lias £it leaet one total [1,k]-set. Finally, we show that finding smallest total [1, k]-set is an NP-complete problem. [ABSTRACT FROM AUTHOR]