Un grafo semisimétrico es un grafo regular transitivo de borde no dirigido que no es transitivo de vértice . En otras palabras, un grafo es semisimétrico si cada vértice tiene el mismo número de aristas incidentes y para cada par de aristas hay una simetría que relaciona una arista con la otra, pero hay un par de vértices para los que no hay simetría. que asigna un vértice a otro.
Un grafo semisimétrico debe ser bipartito y su grupo de automorfismos debe actuar transitivamente en cada una de las dos partes de vértice del grafo bipartito. Por ejemplo, en el gráfico de Folkman que se muestra en el diagrama, los vértices verdes no se pueden asignar a rojo mediante ningún automorfismo, pero dos vértices cualesquiera del mismo color son simétricos entre sí.
Los gráficos semisimétricos fueron estudiados por primera vez por Dauber, un alumno de Frank Harari , en un artículo ahora no disponible titulado "Gráficos simétricos en línea, pero no en puntos". El artículo fue visto por John Folkman, cuyo artículo, publicado en 1967, incluía el gráfico semisimétrico más pequeño, ahora conocido como Gráfico de Folkman , con 20 vértices [1] . El término "semisimétrico" fue utilizado por primera vez por Klin, Lauri y Ziv-Av en un artículo que publicaron en 1978 [2] .
El gráfico semisimétrico cúbico más pequeño (es decir, un gráfico en el que cada vértice incide exactamente en tres aristas) es el gráfico Gray de 54 vértices . Bower [3] fue el primero en descubrir que un gráfico es semisimétrico . El hecho de que el gráfico sea el más pequeño entre los gráficos semisimétricos cúbicos fue demostrado por Marusic y Malnich [4] .
Se conocen todos los gráficos semisimétricos cúbicos hasta 768 vértices. Según Konder, Malnic, Marusic y Potochnik, los cuatro gráficos semisimétricos cúbicos más pequeños después del gráfico de Gray son el gráfico de Ivanov-Iofinova de 110 vértices , el gráfico de Ljubljana de 112 vértices [5] , el gráfico de 120 vértices con circunferencia 8, y el Tatta de 12 celdas [6] .