Samokomplementární graf je graf , který je izomorfní ke svému doplňku . Nejjednodušší netriviální samodoplňkové grafy jsou 4-vrcholová cesta a 5-vrcholový cyklus .
Libovolný Paleyův graf je samodoplňkový [1] . Například věžový graf 3 × 3 ( Paleyův graf devátého řádu) se také samodoplňuje díky symetrii, která udržuje centrální vrchol na místě, ale vyměňuje role středů podél čtyř hran a rohů mříž [2] . Všechny silně pravidelné samokomplementární grafy s méně než 37 vrcholy jsou Paleyovy grafy. Existují však přísně pravidelné grafy s 37, 41 a 49 vrcholy, které nejsou Paleyho grafy [3] .
Rado graf je nekonečný samokomplementární graf.
Samokomplementární graf s n vrcholy má přesně poloviční počet hran úplného grafu , tj. n ( n − 1)/4 hran, a (pokud je více než jeden vrchol) jeho průměr musí být 2 nebo 3 [ 1] . Protože n ( n − 1) musí být dělitelné 4, musí být n shodné s 0 nebo 1 modulo 4. Například graf se 6 vrcholy nemůže být samokomplementární.
Problém kontroly, zda jsou dva samokomplementární grafy izomorfní a kontrola, zda je daný graf samokomplementární, jsou ekvivalentní v době provádění obecnému problému izomorfismu grafu [4] .