Nearly perfect sets in products of graphs

• Autorzy: Kwaśnik M. , 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 maximal if for every vertex u ∈ V(G) - S, S ∪ {u} is not nearly perfect in G. The minimum cardinality of a maximal nearly perfect set is denoted by np(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 np(G1 x G2) and np(G1 ⊗ G2), for some special graphs G1,G2.

Słowa kluczowe

EN

dominating sets; product of graphs

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2004
• Tom: Vol. 24, no. 2
• Strony: 177--180
• Opis fizyczny: Bibliogr. 2 poz.

Twórcy

autor

Kwaśnik M.

• Technical University of Szczecin Institute of Mathematics al. Piastów 48/49, 70-310 Szczecin, Poland

autor

Perl M.

Bibliografia

• [1] Diestel R.: Graph Theory. New York, Springer-Verlag 1997.
• [2] 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.