En el campo matemático de la teoría de grafos , un grafo autocomplementario es un grafo que es isomorfo a su complemento . Los gráficos autocomplementarios no triviales más simples son el gráfico de ruta de 4 vértices y el gráfico de ciclo de 5 vértices . No existe una caracterización conocida de gráficos autocomplementarios.
Cada gráfico de Paley es autocomplementario. [1] Por ejemplo, el gráfico de la torre 3 × 3 (el gráfico 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 gráficos autocomplementarios fuertemente regulares con menos de 37 vértices son gráficos de Paley; sin embargo, hay gráficos fuertemente regulares en 37, 41 y 49 vértices que no son gráficos de Paley. [3]
El gráfico de Rado es un gráfico infinito autocomplementario. [4]
Un gráfico autocomplementario de n -vértices tiene exactamente la mitad de aristas que el gráfico 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 gráfico de 6 vértices no puede ser autocomplementario.
Los problemas de comprobar si dos gráficos autocomplementarios son isomorfos y de comprobar si un gráfico dado es autocomplementario son equivalentes en tiempo polinómico al problema general de isomorfismo de gráficos . [5]