Buscando grafos cúbicos, bipartitos con circunferencia al menos seis y sin ciclos de longitud 8.

Question

Aparte del gráfico de Desargues, ¿hay gráficos agradables (al menos vértice-transitivos), pequeños (digamos, menos de 60 vértices), cúbicos, bipartitos con circunferencia de al menos 6 y no de 8 ciclos? (O, mejor aún, sin ciclos de longitud congruentes a 0 mod 4.)

Bono: ¿alguna idea de cómo utilizar Mathematica para extraer estos de su lista de gráficos que tiene datos para Mathematica 7?

Answer 1

Seguro, la forma de un toro gráfico de la corte de un gran paralelogramo de las baldosas del avión por hexágonos regulares y pegar los lados opuestos juntos. Cualquier ciclo corto tiene una longitud de 6 (uno hex) o de longitud ≥ 10 (dos o más hexes), y haciendo el paralelogramo lo suficientemente grande también puede forzar la noncontractible ciclos a ser tan largo como quieras.

Como para evitar ciclos con longitudes que son múltiplos de cuatro: que estaría en contradicción con la Erdős–Gyárfás conjetura de que los estados que cada gráfico con un grado mínimo de al menos tres tiene un ciclo simple de longitud de una potencia de dos.

Answer 2

El Desargues grafo no tiene ciclos de longitud 8 sin embargo, no es así?

Pero he aquí una bonita 38-vértice bipartito cúbicos de vértice transitiva gráfico no 4 u 8 ciclos:

El gráfico 1, orden de 38. 0 : 1 2 3; 1 : 0 4 7; 2 : 0 6 9; 3 : 0 5 8; 4 : 1 10 13; 5 : 3 11 15; 6 : 2 12 14; 7 : 1 11 16; 8 : 3 12 18; 9 : 2 10 17; 10 : 4 9 28; 11 : 5 7 26; 12 : 6 8 27; 13 : 4 32 35; 14 : 6 34 37; 15 : 5 33 36; 16 : 7 29 35; 17 : 9 31 37; 18 : 8 30 36; 19 : 29 30 31; 20 : 27 32 34; 21 : 28 32 33; 22 : 26 33 34; 23 : 27 30 35; 24 : 28 31 36; 25 : 26 29 37; 26 : 11 22 25; 27 : 12 20 23; 28 : 10 21 24; 29 : 16 19 25; 30 : 18 19 23; 31 : 17 19 24; 32 : 13 20 21; 33 : 15 21 22; 34 : 14 20 22; 35 : 13 16 23; 36 : 15 18 24; 37 : 14 17 25;

Answer 3

Desargues gráfico, también conocida como la generalizada Petersen gráfico de $G(10,3)$ ha circunferencia 6 y también contiene ciclos de longitud 8. Existen tres 10-las jaulas, el más pequeño cúbicos gráficos de la circunferencia de 10. Tienen 70 vértices y ninguno de ellos es el vértice-transitiva. Para obtener más información acerca de la motivación vea aquí.

Por lo tanto, es bastante sorprendente que Gordon ejemplo es tan pequeño. Por cierto, también es arco-transitiva. Se puede considerar como un Levi gráfica de una auto-dual, la bandera transitiva 3-configuración de los 19 puntos y 19 líneas. Configuración contiene triángulos, pero no tiene cuadriláteros.

Aquí está una geométricas realización de este gráfico.

Configuración con triángulos pero no cuadrángulos

1. Una pregunta natural es si este es el más pequeño gráfico con las propiedades requeridas.

2. Otra cuestión es, si existen más pequeños bipartito gráficas si el vértice de la transitividad de la condición se ha caído.