Gráfico simétrico cero

El grafo simétrico cero más pequeño, con 18 vértices y 27 aristas.

El cuboctaedro truncado , un poliedro de simetría cero.

En el campo matemático de la teoría de grafos , un grafo cero-simétrico es un grafo conexo en el que cada vértice tiene exactamente tres aristas incidentes y, para cada par de vértices, existe una simetría única que une un vértice con el otro. Dicho grafo es transitivo en vértices, pero no puede ser transitivo en aristas : el número de simetrías es igual al número de vértices, demasiado pequeño para que todas las aristas se unan a todas las demás. ^{[ 1 ]}

El nombre para esta clase de grafos fue acuñado por RM Foster en una carta de 1966 a HSM Coxeter . ^{[ 2 ]} En el contexto de la teoría de grupos , los grafos cero-simétricos también se denominan representaciones gráficas regulares de sus grupos de simetría. ^{[ 3 ]}

El grafo simétrico cero más pequeño es un grafo no planar con 18 vértices. ^{[ 4 ]} Su notación LCF es [5, − 5] ⁹ .

Entre los grafos planares , los grafos cuboctaédricos truncados e icosidodecaédricos truncados también son simétricos respecto a cero. ^{[ 5 ]}

Todos estos ejemplos son grafos bipartitos . Sin embargo, existen ejemplos más grandes de grafos cero-simétricos que no son bipartitos. ^{[ 6 ]}

Estos ejemplos también tienen tres clases de simetría diferentes (órbitas) de aristas. Sin embargo, existen grafos cero-simétricos con solo dos órbitas de aristas. El grafo más pequeño de este tipo tiene 20 vértices, con notación LCF [6,6,-6,-6] ⁵ . ^{[ 7 ]}

Todo grafo cero-simétrico finito es un grafo de Cayley , una propiedad que no siempre se cumple para los grafos cúbicos vértice-transitivos en general y que ayuda en la solución de tareas de enumeración combinatoria relacionadas con grafos cero-simétricos. Hay 97687 grafos cero-simétricos con hasta 1280 vértices. Estos grafos forman el 89% de los grafos cúbicos de Cayley y el 88% de todos los grafos cúbicos vértice-transitivos conexos con el mismo número de vértices. ^{[ 8 ]}

Todos los grafos cero-simétricos conexos finitos conocidos contienen un ciclo hamiltoniano , pero se desconoce si todo grafo cero-simétrico conexo finito es necesariamente hamiltoniano. ^{[ 9 ]} Este es un caso especial de la conjetura de Lovász que afirma que (con cinco excepciones conocidas, ninguna de las cuales es cero-simétrica) todo grafo conexo transitivo de vértices finito y todo grafo de Cayley finito es hamiltoniano.

• Grafo semisimétrico : grafos que presentan simetría entre cada par de aristas, pero no entre cada par de vértices (invirtiendo los roles de aristas y vértices en la definición de grafos cero-simétricos).