En el campo matemático de la teoría de grafos , un grafo G es simétrico (o arco-transitivo ) si, dados dos pares de vértices adyacentes u 1 — v 1 y u 2 — v 2 de G , existe un automorfismo
de tal manera que
En otras palabras, un grafo es simétrico si su grupo de automorfismos actúa transitivamente sobre pares ordenados de vértices adyacentes (es decir, sobre aristas consideradas como si tuvieran una dirección). [2] A este tipo de grafo a veces también se lo denomina 1-arco -transitivo [2] o flag-transitivo . [3]
Por definición (ignorando u 1 y u 2 ), un grafo simétrico sin vértices aislados también debe ser transitivo por vértices . [1] Dado que la definición anterior asigna una arista a otra, un grafo simétrico también debe ser transitivo por aristas . Sin embargo, un grafo transitivo por aristas no necesita ser simétrico, ya que a—b podría asignarse a c—d , pero no a d—c . Los grafos en estrella son un ejemplo simple de ser transitivo por aristas sin ser transitivo por vértices o simétricos. Como otro ejemplo, los grafos semisimétricos son transitivos por aristas y regulares , pero no transitivos por vértices.
Por lo tanto, todo grafo simétrico conexo debe ser transitivo por vértices y transitivo por aristas, y lo inverso es cierto para grafos de grado impar . [3] Sin embargo, para grado par , existen grafos conexos que son transitivos por vértices y transitivos por aristas, pero no simétricos. [4] Dichos grafos se denominan semitransitivos . [5] El grafo semitransitivo conexo más pequeño es el grafo de Holt , con grado 4 y 27 vértices. [1] [6] De manera confusa, algunos autores usan el término "grafo simétrico" para referirse a un grafo que es transitivo por vértices y transitivo por aristas, en lugar de un grafo arcotransitivo. Tal definición incluiría grafos semitransitivos, que están excluidos de la definición anterior.
Un grafo transitivo de distancia es aquel en el que, en lugar de considerar pares de vértices adyacentes (es decir, vértices separados por una distancia de 1), la definición cubre dos pares de vértices, cada uno con la misma distancia entre sí. Dichos grafos son automáticamente simétricos, por definición. [1]
Un t -arco se define como una secuencia de t + 1 vértices, de modo que dos vértices consecutivos cualesquiera en la secuencia son adyacentes, y con cualquier vértice repetido estando separado por más de 2 pasos. Un grafo t -transitivo es un grafo tal que el grupo de automorfismos actúa transitivamente sobre t -arcos , pero no sobre ( t + 1 )-arcos . Dado que los 1-arcos son simplemente aristas, cada grafo simétrico de grado 3 o más debe ser t -transitivo para algún t , y el valor de t se puede utilizar para clasificar aún más los grafos simétricos. El cubo es 2-transitivo , por ejemplo. [1]
Nótese que, convencionalmente, el término "gráfico simétrico" no es complementario del término " gráfico asimétrico ", ya que este último se refiere a un gráfico que no tiene simetrías no triviales en absoluto.
Dos familias básicas de grafos simétricos para cualquier número de vértices son los grafos cíclicos (de grado 2) y los grafos completos . Otros grafos simétricos están formados por los vértices y las aristas de los poliedros regulares y cuasirregulares: el cubo , el octaedro , el icosaedro , el dodecaedro , el cuboctaedro y el icosidodecaedro . La extensión del cubo a n dimensiones da los grafos hipercubicos (con 2 n vértices y grado n). De manera similar, la extensión del octaedro a n dimensiones da los grafos de los politopos cruzados , esta familia de grafos (con 2n vértices y grado 2n-2) a veces se denominan grafos de cóctel - son grafos completos con un conjunto de aristas que hacen una correspondencia perfecta eliminada. Otras familias de grafos simétricos con un número par de vértices 2n son los grafos bipartitos completos con división uniforme K n,n y los grafos corona con 2n vértices. Muchos otros grafos simétricos pueden clasificarse como grafos circulantes (pero no todos).
El gráfico de Rado constituye un ejemplo de un gráfico simétrico con infinitos vértices y grado infinito.
La combinación de la condición de simetría con la restricción de que los grafos sean cúbicos (es decir, que todos los vértices tengan grado 3) produce una condición bastante fuerte, y dichos grafos son lo suficientemente raros como para ser enumerados. Todos tienen un número par de vértices. El censo de Foster y sus extensiones proporcionan dichas listas. [7] El censo de Foster fue iniciado en la década de 1930 por Ronald M. Foster mientras trabajaba en Bell Labs , [8] y en 1988 (cuando Foster tenía 92 [1] ) se publicó en forma de libro el censo de Foster entonces vigente (que enumera todos los grafos cúbicos simétricos de hasta 512 vértices). [9] Los primeros trece elementos de la lista son grafos cúbicos simétricos con hasta 30 vértices [10] [11] (diez de ellos también son transitivos en cuanto a la distancia ; las excepciones son las indicadas):
Otros grafos cúbicos simétricos conocidos son el grafo de Dyck , el grafo de Foster y el grafo de Biggs-Smith . Los diez grafos transitivos de distancia enumerados anteriormente, junto con el grafo de Foster y el grafo de Biggs-Smith , son los únicos grafos cúbicos transitivos de distancia.
La conectividad de vértices de un grafo simétrico es siempre igual al grado d . [3] Por el contrario, para los grafos transitivos de vértices en general, la conectividad de vértices está limitada por debajo por 2( d + 1)/3. [2]
Un grafo t -transitivo de grado 3 o más tiene una circunferencia de al menos 2( t – 1). Sin embargo, no hay grafos t -transitivos finitos de grado 3 o más para t ≥ 8. En el caso de que el grado sea exactamente 3 (grafos cúbicos simétricos), no hay ninguno para t ≥ 6.
