En el campo matemático de la teoría de grafos , un grafo autocomplementario es un grafo que es isomorfo a su complemento . Los grafos autocomplementarios no triviales más simples son el grafo de trayectoria de 4 vértices y el grafo de ciclo de 5 vértices . No se conoce ninguna caracterización de los grafos autocomplementarios.
Todo grafo de Paley es autocomplementario. [1] Por ejemplo, el grafo de la torre de 3 × 3 (el grafo de Paley de orden nueve) es autocomplementario, por una simetría que mantiene el vértice central en su lugar pero intercambia los roles de los cuatro puntos medios laterales y las cuatro esquinas de la cuadrícula. [2] Todos los grafos autocomplementarios fuertemente regulares con menos de 37 vértices son grafos de Paley; sin embargo, hay grafos fuertemente regulares en 37, 41 y 49 vértices que no son grafos de Paley. [3]
El gráfico de Rado es un gráfico autocomplementario infinito. [4]
Un grafo autocomplementario de n vértices tiene exactamente la mitad de aristas que el grafo completo , es decir, n ( n − 1)/4 aristas, y (si hay más de un vértice) debe tener un diámetro de 2 o 3. [1] Dado que n ( n − 1) debe ser divisible por 4, n debe ser congruente con 0 o 1 módulo 4; por ejemplo, un grafo de 6 vértices no puede ser autocomplementario.
Los problemas de comprobar si dos grafos autocomplementarios son isomorfos y de comprobar si un grafo dado es autocomplementario son equivalentes en tiempo polinomial al problema general de isomorfismo de grafos . [5]