Gráfico autocomplementario

En el campo matemático de la teoría de grafos , un grafo autocomplementario es un grafo isomorfo a su complemento . Los grafos autocomplementarios no triviales más simples son el grafo camino de 4 vértices y el grafo ciclo de 5 vértices .

Todo grafo de Paley es autocomplementario. ^{[ 1 ]} Por ejemplo, el grafo de torres de 3 × 3 (el grafo de Paley de orden nueve) es autocomplementario, debido a 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, existen grafos fuertemente regulares con 37, 41 y 49 vértices que no son grafos de Paley. ^{[ 3 ]}

El grafo de Rado es un grafo 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 ]}

• Weisstein, Eric W. , "Grafo autocomplementario" , MathWorld