La construcción de la auto-complementarios de gráficos

Question

¿Cómo se hace de forma sistemática la construcción de una auto-complementarios gráfico, en el decir de 8 vértices?

[Añadido: tal vez los demás lo saben ya, pero yo tuve que buscar mi conjetura para asegurarse de que estaba en lo correcto: un auto-complementarios gráfico es un gráfico simple que es isomorfo a su complemento. --PLC]

Answer 1

Aquí un pequeño algoritmo para la construcción de una auto-complementarios gráfico de un auto-complementarios gráfico de $H$ $4k$ o $4k+1$ vértices, $k = 1, 2, ...$ (por ejemplo, de un auto-complementarios gráfico con $4$ vértices, se puede construir un auto-complementarios gráfico con $8$ vértices; de $5$ vértices, la construcción de un con $9$ vértices).

Ver este PDF en la construcción de la auto-complementarios de gráficos.

Answer 2

Sistemáticamente es fácil; de forma sistemática y eficiente, no sé. Es fácil trabajar en cuántas aristas de un grafo debe tener, es un comienzo. También hay algo de información en http://oeis.org/A000171

Answer 3

Si usted tiene un auto-complementarios gráfico de orden 4n, la mitad de los vértices deben cada mentira en menos de 2n bordes y la otra mitad debe estar en 2n o más aristas. Agregar un vértice mediante la conexión a 2n vértices acostado en menos de 2n bordes. El resultado es un auto-complementarios gráfico de orden 4n+1.

Usted puede crear un segundo auto-complementarios gráfico de orden 4n+1 tomando la auto-complementarios gráfico de orden 4n y conectar el nuevo punto a la 2n vértices acostado en 2n o más aristas.