En el campo matemático de la teoría de grafos , un grafo semisimétrico es un grafo no dirigido que es transitivo por aristas y regular , pero no transitivo por vértices . En otras palabras, un grafo es semisimétrico si cada vértice tiene el mismo número de aristas incidentes, y existe una simetría que lleva cualquiera de las aristas del grafo a cualquiera de sus otras aristas, pero hay algún par de vértices tal que ninguna simetría mapea el primero en el segundo.
Un grafo semisimétrico debe ser bipartito y su grupo de automorfismos debe actuar transitivamente sobre cada uno de los dos conjuntos de vértices de la bipartición (de hecho, no se requiere regularidad para que se cumpla esta propiedad). Por ejemplo, en el diagrama del grafo de Folkman que se muestra aquí, los vértices verdes no pueden mapearse a los rojos mediante ningún automorfismo, pero cada dos vértices del mismo color son simétricos entre sí.
Los grafos semisimétricos fueron estudiados por primera vez por E. Dauber, un estudiante de F. Harary, en un artículo, ya no disponible, titulado "On line- but not point-symmetry graphs". Esto fue visto por Jon Folkman , cuyo artículo, publicado en 1967, incluye el grafo semisimétrico más pequeño, ahora conocido como el grafo de Folkman , en 20 vértices. [1] El término "semi-simétrico" fue utilizado por primera vez por Klin et al. en un artículo que publicaron en 1978. [2]
El grafo cúbico semisimétrico más pequeño (es decir, aquel en el que cada vértice incide exactamente en tres aristas) es el grafo de Gray de 54 vértices. Bouwer (1968) fue el primero en observar que era semisimétrico. Dragan Marušič y Aleksander Malnič demostraron que era el grafo cúbico semisimétrico más pequeño . [3]
Se conocen todos los grafos cúbicos semisimétricos de hasta 10000 vértices. Según Conder , Malnič, Marušič y Potočnik, los cuatro grafos cúbicos semisimétricos más pequeños posibles después del grafo de Gray son el grafo de Iofinova-Ivanov de 110 vértices, el grafo de Ljubljana de 112 vértices, [4] un grafo de 120 vértices con circunferencia 8 y el grafo de Tutte de 12 jaulas . [5]