Recuento de máxima toroidal gráficos

Question

Considerar la secuencia de A006822, el Número de conectados regular gráficos de grado 6 con n nodos, 1, 1, 4, 21, 266, 7849, 367860, 21609300, 1470293675, 113314233808, 9799685588936.

Se inicia con un gráfico de 7 vértices, $K_7$, que es la máxima toroidal gráfico (género 1). Se puede dibujar en un toro sin bordes de cruce y todas las caras triangulares. Mapa para Colorear sobre un Toro hizo la primera imagen. Incrustaciones de Gráficos en un Toro hizo el segundo y subsiguientes imágenes.

El 8 de nodo sextic gráfico, el 16-gráfico de la célula es máxima toroidal.

Cuatro sextic gráficos en 9 vértices. No estoy seguro de si $9_1$ $9_2$ son toroidal. {"CompleteTripartite", {3, 3, 3}} el gráfico y el {"Circulantes", {9, {1, 2, 3}}} gráfico son tanto toroidal.

Hay 21 10-nodo sextic gráficos. No sé que son toroidal.

Hay una buena manera para encontrar cuál de estos gráficos son de máxima toroidal gráfico para que podamos iniciar el entero de la secuencia? Un método que se me ocurrió: el conteo de los 3-ciclos. Si no hay, al menos, $2 V$ 3-ciclos, no habrá suficiente caras para el toro.

NUEVO: Arriba, para 7,8,9 vértices que tienen una secuencia que se inicia 1,1,2. Que parece ser la secuencia de A129033. $(1, 1, 2, 1, 1, 4, 2, 2, 4, 5, 2, ...)$. Que coincide con surftri cuenta, también mencionado en la Generación de las Triangulaciones.

El Paley-13 gráfico es también un 134-circulantes gráfico que puede ser representado como la siguiente. Otros ejemplos en el Triangular de las cuadrículas en un toro

No todos malla triangular gráficos son circulantes, con la Shrikhande gráfica de un ejemplo. Una notación que se encarga tanto de la circulantes y Shrikhande es necesario.

Aquí está una cuadrícula de $V$, A129033, y no equivalentes circulantes gráficos. El toroidal sextics será una subconjuntos de circulants y Shrikhande-como ejemplos.

Answer 1

Si tenemos un toroidal de la inserción de un gráfico de $G$, la eliminación de cualquier vértice $v$ produce un hexagonal de la cara, que es un $6$ciclo $C(v)$ a través de $v$'s $6$ vecinos. Determinar el $C(v)$ por cada vértice $v$ da suficiente información para reconstruir la incrustación de objetos: las caras que contienen $v$ son precisamente los triángulos $uvw$ donde $uw$ es un borde de $C(v)$. Así podemos tratar de encontrar una incrustación mediante la selección de $C(v)$ por cada $v$.

Estos deben ser coherentes: si $uw$ es un borde de $C(v)$, $vw$ debe ser un borde de $C(u)$ $uv$ debe ser un borde de $C(w)$. Por otra parte, cada borde de la $xy$ $G$ tiene que aparecer exactamente $2$ estos $6$ciclos: si $xy$ es el borde entre triángulos $vxy$$wxy$, aparece en $C(v)$ $C(w)$ solamente. Una vez que está satisfecho, le hemos incorporado $G$ sobre una superficie de género $0$...

...lo que significa que una comprobación final tenemos que hacer es si hemos integrado a $G$ sobre un toro o en una botella de Klein. (En este punto, tenemos las caras, de modo que todo lo que tenemos que hacer es tratar de orientar ellos: dar a cada triángulo de las agujas del reloj o en el sentido contrario de orientación para que cada borde se recorre en direcciones opuestas por sus dos triángulos. Esto es posible en el toro, pero no en la botella de Klein.)

Por ejemplo, aquí es la razón por la $9_1$ no es toroidal. Si nos fijamos en los subdiagramas inducida por los vecinos de cada una de las $9$ vértices, se obtiene el $9$ gráficos a continuación:

Los barrios de vértices $3, 4, 5, 6, 7$ todos tienen la misma forma, con los bordes de $12$ $89$ en los lados. Para cada uno de los gráficos, los bordes de $12$ $89$ tiene que aparecer en una $6$-ciclo a través de los vecinos: por ejemplo, en el barrio de $3$, utilizamos el borde de la $12$ o tendríamos que recoger $14, 15, 24, 25$ (ya que esos son los únicos otros vecinos de $1$$2$), lo cual crearía un $4$-ciclo. Esto no produce una incrustación, ya que los bordes $12$ $89$ aparecen en demasiadas caras.

$9_2$ no se producen contradicciones similares; por la mano, me las he arreglado para encontrar una incrustación de objetos (el proceso es similar a la solución de un rompecabezas de Sudoku), pero resultó ser no-orientable. Hice un par de opciones arbitrarias a lo largo del camino, así que es posible que un toroidal de la incorporación de la $9_2$ existe; este proceso debería ser hecho por ordenador (y no debería ser demasiado difícil de código).