Question

Fie G si H grafuri simple conexe avand | centr(G) | <= | centr(H) | . Sa se demonstreze ca urmatoarele afirmatii sunt echivalente:
- ck(G×H) = G×H ;
- | centr(G) | = 1 si ck(H) = H .

Answer 1

Afirmatiile sunt echivalente datorita faptului ca produsul cartezian al grafurilor G si H (denotat G x H) este format din toate perechile posibile de noduri (v,w) unde v este un nod din G si w este un nod din H.

Daca ck(G x H) = G x H, inseamna ca toate perechile de noduri formate din centrul lui G si orice nod din H sunt conexe. Acest lucru se intampla doar daca |centr(G)| = 1, deoarece, in acest caz, centrul lui G va fi singurul nod din G care va fi conectat cu orice nod din H.

In cazul in care |centr(G)| = 1 si ck(H) = H, inseamna ca centrul lui G este conectat cu orice nod din H si ca orice nod din H este conectat cu orice alt nod din H. Acest lucru se traduce prin faptul ca ck(G x H) = G x H.