En el campo matemático de la teoría de grafos , un grafo semi-simétrico es un grafo no dirigido que es transitivo por aristas y regular , pero no transitivo por vértice . En otras palabras, una gráfica es semi-simétrica si cada vértice tiene el mismo número de aristas incidentes, y hay una simetría que lleva cualquiera de las aristas del grafo a cualquier otra arista, pero hay algún par de vértices tal que no hay simetría asigna el primero al segundo.
Familias de gráficos definidas por sus automorfismos | ||||
---|---|---|---|---|
distancia-transitiva | → | distancia regular | ← | muy regular |
↓ | ||||
simétrico (arco-transitivo) | ← | t -transitivo, t ≥ 2 | simétrico sesgado | |
↓ | ||||
(si está conectado) vértice y borde transitivo | → | edge-transititive y regular | → | borde transitivo |
↓ | ↓ | ↓ | ||
vértice-transitivo | → | regular | → | (si es bipartito) birregular |
↑ | ||||
Gráfico de Cayley | ← | simétrico cero | asimétrico |
Propiedades
Un gráfico semi-simétrico debe ser bipartito , y su grupo de automorfismo debe actuar de manera transitiva en cada uno de los dos conjuntos de vértices de la bipartición (de hecho, no se requiere regularidad para que se mantenga esta propiedad). Por ejemplo, en el diagrama del gráfico de Folkman que se muestra aquí, los vértices verdes no se pueden asignar a los rojos mediante ningún automorfismo, pero cada dos vértices del mismo color son simétricos entre sí.
Historia
Las gráficas semi-simétricas fueron estudiadas por primera vez por E. Dauber, un estudiante de F. Harary, en un artículo, que ya no está disponible, titulado "Gráficas simétricas en líneas pero no puntuales". Esto fue visto por Jon Folkman , cuyo artículo, publicado en 1967, incluye el gráfico semisimétrico más pequeño, ahora conocido como el gráfico 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]
Gráficos cúbicos
El gráfico semi-simétrico cúbico más pequeño (es decir, uno en el que cada vértice incide exactamente en tres aristas) es el gráfico de Gray en 54 vértices. Bouwer (1968) observó por primera vez que era semisimétrico . Dragan Marušič y Aleksander Malnič demostraron que era el gráfico semi-simétrico cúbico más pequeño . [3]
Se conocen todas las gráficas cúbicas semi-simétricas de hasta 768 vértices. Según Conder , Malnič, Marušič y Potočnik, los cuatro gráficos cúbicos semi-simétricos más pequeños posibles después del gráfico de Gray son el gráfico Iofinova-Ivanov en 110 vértices, el gráfico de Ljubljana en 112 vértices, [4] un gráfico en 120 vértices con circunferencia 8 y el Tutte 12-jaula . [5]
Referencias
- ^ Folkman, J. (1967), "Gráficos simétricos de líneas regulares", Journal of Combinatorial Theory , 3 (3): 215-232, doi : 10.1016 / S0021-9800 (67) 80069-3.
- ^ Klin, Lauri y Ziv-Av (2011). "Vínculos entre dos gráficos semisimétricos en 112 vértices a través de la lente de los esquemas de asociación" (PDF) . Consultado el 17 de agosto de 2015 . Cite journal requiere
|journal=
( ayuda ) - ^ Bouwer, IZ (1968), "Un borde pero no un gráfico cúbico transitivo de vértice", Canadian Mathematical Bulletin , 11 (4): 533–535, doi : 10.4153 / CMB-1968-063-0.
- ^ Conder, M .; Malnič, A .; Marušič, D .; Pisanski, T .; Potočnik, P. (2002), "The Ljubljana Graph" (PDF) , IMFM Preprints , Ljubljana: Instituto de Matemáticas, Física y Mecánica, 40 (845).
- ^ Conder, Marston ; Malnič, Aleksander; Marušič, Dragan ; Potočnik, Primož (2006), "Un censo de gráficos cúbicos semisimétricos de hasta 768 vértices", Journal of Algebraic Combinatorics , 23 (3): 255–294, doi : 10.1007 / s10801-006-7397-3.
enlaces externos
- Weisstein, Eric W. "Gráfico semisimétrico" . MathWorld .