Nearly perfect sets in the n-fold products of graphs

• Autorzy: Perl M.
• Języki publikacji: EN

Abstrakty

EN

The study of nearly perfect sets in graphs was initiated in [2], Let S ⊆ 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 ∈ V(G) - S, S ∪ {u} is not nearly perfect in G. We denote the minimum cardinality of a 1-maximal nearly perfect set in G by np(G). We will call the 1-maximal nearly perfect set of the cardinality np(G) an np(G) - set. In this paper, we evaluate the parameter np(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.

Słowa kluczowe

EN

dominating sets; product of graphs

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2007
• Tom: Vol. 27, no. 1
• Strony: 83--88
• Opis fizyczny: Bibliogr. 3 poz.

Twórcy

autor

Perl M.

• Szczecin University of Technology, Institute of Mathematics, al. Piastów 48/49, Szczecin, Poland,

Bibliografia

• [1] R. Diestel, Graph Theory, Springer-Verlag, New York, 1997.
• [2] 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.
• [3] M. Kwaśnik, M. Perl, Nearly perfect sets in products of graphs, Opuscula Mathematica 24/2 (2004), 177-180.