Opuscula Mathematica (Jan 2007)
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, Nearly perfect sets in graphs, 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.
