TY  - JOUR
ID  - Kwaśnik2004
LB  - Kwaśnik2004
AU  - Kwaśnik, Maria
AU  - Perl, Monika
TI  - Nearly perfect sets in products of graphs
ST  - Nearly perfect sets in products of graphs
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2004
VL  - 24
IS  - 2
SP  - 177
EP  - 180
DO  - http://dx.doi.org/10.7494/OpMath.2004.24.2.177
UR  - http://dx.doi.org/10.7494/OpMath.2004.24.2.177
AB  - The study of nearly perfect sets in graphs was initiated in [Dunbar J. E., Harris F. C., Hedetniemi S. M., Hedetniemi S. T., McRae A. A., Laskar R. C.: 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 maximal if for every vertex \(u\in V(G)-S\), \(S\cup \{u\}\) is not nearly perfect in \(G\). The minimum cardinality of a maximal nearly perfect set is denoted by \(n_p(G)\). It is our purpose in this paper to determine maximal nearly perfect sets in two well-known products of two graphs; i.e., in the Cartesian product and in the strong product. Lastly, we give upper bounds of \(n_p(G_1\times G_2)\) and \(n_p(G_1\otimes G_2)\), for some special graphs \(G_1\), \(G_2\).
KW  - dominating sets
KW  - product of graphs
SN  - 1232-9274
ER  -