Itseään täydentävä graafi on graafi , joka on isomorfinen komplementtinsa kanssa . Yksinkertaisimmat ei-triviaalit itsetä täydentävät graafit ovat 4-pisteinen polku ja 5-pisteinen sykli .
Mikä tahansa Paley-graafi on itseään täydentävä [1] . Esimerkiksi 3 × 3 tornin graafi (yhdeksännen kertaluvun Paley-graafi) täydentää myös itseään symmetrian vuoksi, joka pitää keskipisteen paikoillaan, mutta vaihtaa keskipisteiden rooleja pitkin neljää reunaa ja kulmia. hila [2] . Kaikki vahvasti säännölliset itseään täydentävät graafit, joissa on alle 37 kärkeä, ovat Paley-graafia. On kuitenkin olemassa tiukasti säännöllisiä graafisia 37, 41 ja 49 kärkeä, jotka eivät ole Paley-graafia [3] .
Rado-graafi on ääretön itseään täydentävä graafi.
Itsekomplementaarisessa graafissa, jossa on n kärkeä, on täsmälleen puolet täydellisen graafin reunojen lukumäärästä , eli n ( n − 1)/4 reunaa, ja (jos pisteitä on enemmän kuin yksi) sen halkaisijan on oltava joko 2 tai 3 [ 1] . Koska n ( n − 1) on jaollinen 4:llä, n: n on oltava kongruentti 0:n tai 1:n modulo 4:n kanssa. Esimerkiksi graafi, jossa on 6 kärkeä, ei voi olla itseään täydentävä.
Ongelma tarkistaa, ovatko kaksi itseään täydentävää graafia isomorfisia ja tarkistaa, onko tietty graafi itsekomplementaarinen, vastaavat suoritusajaltaan yleistä graafin isomorfismiongelmaa [4] .