TY  - JOUR
ID  - Perl2007
LB  - Perl2007
AU  - Perl, Monika
TI  - Nearly perfect sets in the n-fold products of graphs
ST  - Nearly perfect sets in the n-fold products of graphs
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2007
VL  - 27
IS  - 1
SP  - 83
EP  - 88
DO  - http://dx.doi.org/10.7494/OpMath.2007.27.1.83
UR  - http://dx.doi.org/10.7494/OpMath.2007.27.1.83
AB  - 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.
KW  - dominating sets
KW  - product of graphs
SN  - 1232-9274
ER  -