Nearly perfect sets in the n-fold products of graphs

Abstract

The study of nearly perfect sets in graphs was initiated in [J. E. Dunbar, F. C. Harris, S. M. Hedetniemi, S. T. Hedetniemi, A. A. McRae, R. C. Laskar, <i>Nearly perfect sets in graphs</i>, Discrete Mathematics 138 (1995), 229-246]. Let $S \subseteq V(G)$. We say that $S$ is a nearly perfect set (or is nearly perfect) in $G$ if every vertex in $V(G)-S$ is adjacent to at most one vertex in $S$. A nearly perfect set $S$ in $G$ is called $1$-maximal if for every vertex $u \in V(G)-S$, $S \cup \{u\}$ is not nearly perfect in $G$. We denote the minimum cardinality of a $1$-maximal nearly perfect set in $G$ by $n_{p}(G)$. We will call the $1$-maximal nearly perfect set of the cardinality $n_{p}(G)$ an $n_{p}G)$-set. In this paper, we evaluate the parameter $n_{p}(G)$ for some $n$-fold products of graphs. To this effect, we determine $1$-maximal nearly perfect sets in the $n$-fold Cartesian product of graphs and in the $n$-fold strong product of graphs.