Grafo autocomplementario

El estilo de esta traducción aún no ha sido revisado por terceros. Si eres hispanohablante nativo y no has participado en esta traducción puedes colaborar revisando y adaptando el estilo de ésta u otras traducciones ya acabadas.

Un grafo autocomplementario: el grafo azul N es isomorfo a su complemento, el grafo rojo con línea punteada Z.

Un grafo autocomplementario es un grafo que es isomorfo a su complemento. Los grafos autocomplementarios más simples son el camino de 4 vértices y el ciclo de 5 vértices.

Los grafos autocomplementarios funcionan por su relación con el problema de isomorfismo de grafos: determinar si dos grafos autocomplementarios son isomorfos y determinar si un grafo dado es autocomplementario son polinómicamente equivalentes al problema general de isomorfismo de grafos.^[1]

Un grafo autocomplementario de n vértices tiene exactamente la mitad de aristas de su grafo completo, en este caso, n(n − 1)/4 aristas, y (si tiene más de un vértice) debe tener diámetro 2 o 3.^[2] Como n(n −1) debe ser divisible por 4, n debe ser congruente con 0 o 1 mod 4; por ejemplo, un grafo de 6 vértices no puede ser autocomplementario.

Todo grafo de Paley es autocomplementario.^[2] Todo grafo fuertemente regular y autocomplementario con menos de 37 vértices es un grafo de Paley; pero, hay grafos fuertemente regulares con 37, 41 y 49 vértices que no son grafos de Paley.^[3]

El grafo de Rado es un grafo infinito autocomplementario.

Referencias

1. ↑ Colbourn, Marlene J.; Colbourn, Charles J. (1978), «Graph isomorphism and self-complementary graphs», SIGACT News 10 (1): 25–29, doi:10.1145/1008605.1008608 .
2. ↑ ^{a b} Sachs, Horst (1962), «Über selbstkomplementäre Graphen», Publicationes Mathematicae Debrecen 9: 270–288, Plantilla:MR .
3. ↑ Rosenberg, I. G. (1982), «Regular and strongly regular selfcomplementary graphs», Theory and practice of combinatorics, North-Holland Math. Stud., 60, Amsterdam: North-Holland, pp. 223–238, Plantilla:MR .