Komplementer gráf

A Wikipédiából, a szabad enciklopédiából
A Petersen-gráf a bal oldalon és komplementere a jobb oldalon

Valamely gráf komplementer gráfja az a gráf, amelynek csúcshalmaza megegyezik a G gráf csúcshalmazával, az élhalmaza pedig a G gráf élhalmazának a komplementer halmaza (a teljes gráf élhalmazára, mint alaphalmazra nézve).

Definíció[szerkesztés]

A gráf komplementere a gráf, ha tetszőleges csúcsokra fennáll, hogy

Elemi tulajdonságok[szerkesztés]

Egyszerű megfontolásokkal adódnak az alábbi összefüggések a komplementer gráf fokszámaira:

, ahol u egy tetszőleges csúcsot jelöl.

illetve a komplementer gráf éleinek számosságára:

.