Opuscula Math. 27, no. 1 (2007), 83-88

Opuscula Mathematica

# Nearly perfect sets in the n-fold products of graphs

Monika Perl

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.

Keywords: dominating sets, product of graphs.

Mathematics Subject Classification: 05C69, 05C70.

Full text (pdf)