ACOPERIREA CONVEXĂ MINIMĂ A GRAFURILOR SPECIALE NEORIENTATE

Radu BUZATU State University of Moldova

Rezumat

Mulţimea de vârfuri S ale grafului G se numeşte convexă dacă pentru orice două vârfuri x, y din S toate vârfurile ce aparţin tuturor lanţurilor de lungime minimă cu extremităţile x, y se conţin în S. Se spune că G conţine o p-acoperire convexă dacă X(G) poate fi acoperită cu p mulţimi convexe. Numărul acoperirii convexe al lui G este cel mai mic număr p  2, pentru care G conţine o p-acoperire convexă. În particular, numărul acoperirii convexe netriviale al lui G este cel mai mic număr p  2, pentru care G conţine o p-acoperire convexă, în care orice mulţime constă din cel puţin 3 vârfuri. În această lucrare noi determinăm numărul acoperirii convexe şi numărul acoperirii convexe netriviale al unor clase speciale de grafuri obţinute din următoarele operaţii pe grafuri: suma, produsul cartezian, produsul lexicografic, coroana. Cuvinte-cheie: grafuri neorientate, acoperiri convexe, numărul acoperirii convexe, operaţii, suma grafurilor, produs cartezian, produs lexicografic, coroană.