Encontrar un gráfico autocomplementario con $v = 8$ . De los $12, 346$ gráficos con $v = 8$ sólo cuatro son autocomplementarios.

Question

Este es el ejercicio 2.16 de Trudeau:

Encontrar un gráfico autocomplementario con $v = 8$ . De los $12, 346$ gráficos con $v = 8$ sólo cuatro son autocomplementarios.

La imagen de abajo es la respuesta que da el propio libro:

Y la imagen de abajo es la respuesta que he encontrado:

Dado que el libro dice que hay sólo cuatro gráficos que son autocomplementarios con $v = 8$ ¿descubrí dos nuevos o mis gráficos son de alguna manera isomorfos a los que proporciona el libro?

Nota: Mis gráficos están dibujados con sus complementos en una sola figura, de ahí los diferentes colores.

Si mis grafos son isomorfos a los proporcionados por el libro, ¿podría proporcionar las etiquetas de los vértices que los hacen isomorfos? ¿Dónde está mi error?

Gracias de antemano.

Answer 1

El gráfico de la izquierda es Fanny. Encontrarás los isomorfismos haciendo coincidir los vértices de grado 2.

El gráfico de la derecha no es ninguno de los cuatro.

Obsérvese que la OEIS dice que hay 10 grafos autocomplementarios en 8 vértices https://oeis.org/A000171 . Se muestran en http://mathworld.wolfram.com/Self-ComplementaryGraph.html De hecho, su gráfico de la imagen de la derecha aparece allí como "gráfico autocomplementario 3".

Answer 2

Para complementar la respuesta de Michal, puedes ver que tu gráfico izquierdo es Fanny Zambuto manteniendo las relaciones de borde que tienes, pero permutando las ubicaciones $A \mapsto C \mapsto E \mapsto G \mapsto A$ .