En el campo matemático de la teoría de grafos , un grafo G es simétrico (o transitivo en arco ) si, dados dos pares cualesquiera de vértices adyacentes u 1 — v 1 y u 2 — v 2 de G , existe un automorfismo.
tal que
En otras palabras, un gráfico es simétrico si su grupo de automorfismo actúa transitivamente sobre pares ordenados de vértices adyacentes (es decir, sobre aristas que se considera que tienen una dirección). [2] Este tipo de gráfico a veces también se denomina transitivo de 1 arco [2] o transitivo de bandera . [3]
Por definición (ignorando u 1 y u 2 ), un gráfico simétrico sin vértices aislados también debe ser transitivo por vértices . [1] Dado que la definición anterior asigna un borde a otro, un gráfico simétrico también debe ser transitivo de borde . Sin embargo, un gráfico transitivo de aristas no tiene por qué ser simétrico, ya que a—b podría asignarse a c—d , pero no a d—c . Los gráficos de estrellas son un ejemplo simple de ser transitivos de borde sin ser transitivos de vértice o simétricos. Como ejemplo adicional, los gráficos semisimétricos son transitivos de borde y regulares , pero no transitivos de vértice.
Por lo tanto, todo gráfico simétrico conectado debe ser transitivo por vértice y transitivo por aristas, y lo contrario es cierto para los gráficos de grado impar . [3] Sin embargo, para grados pares , existen gráficos conectados que son transitivos por vértice y transitivos por aristas, pero no simétricos. [4] Estos gráficos se denominan semitransitivos . [5] El gráfico semitransitivo conectado más pequeño es el gráfico de Holt , con grado 4 y 27 vértices. [1] [6] De manera confusa, algunos autores usan el término "gráfico simétrico" para referirse a un gráfico transitivo por vértices y transitivo por aristas, en lugar de un gráfico transitivo por arco. Tal definición incluiría grafos semitransitivos, que están excluidos de la definición anterior.
Un gráfico de distancia transitiva 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 de ellos a la misma distancia. Estos gráficos son automáticamente simétricos, por definición. [1]
Un arco t se define como una secuencia de t + 1 vértices, de modo que dos vértices consecutivos cualesquiera de la secuencia sean adyacentes y los vértices repetidos estén separados por más de 2 pasos. Un gráfico t -transitivo es un gráfico tal que el grupo de automorfismo actúa transitivamente en t -arcos , pero no en ( t + 1 )-arcos . Dado que los 1 arcos son simplemente aristas, cada gráfico simétrico de grado 3 o más debe ser t -transitivo para alguna t , y el valor de t se puede utilizar para clasificar aún más los gráficos simétricos. El cubo es 2-transitivo , por ejemplo. [1]
Tenga en cuenta 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 ninguna simetría no trivial.
Dos familias básicas de gráficas simétricas para cualquier número de vértices son las gráficas de ciclo (de grado 2) y las gráficas completas . Otros gráficos simétricos están formados por los vértices y aristas de los poliedros regulares y cuasiregulares: el cubo , el octaedro , el icosaedro , el dodecaedro , el cuboctaedro y el icosidodecaedro . La extensión del cubo a n dimensiones da las gráficas de hipercubo (con 2 n vértices y grado n). De manera similar, la extensión del octaedro a n dimensiones da las gráficas de los politopos cruzados ; esta familia de gráficas (con 2n vértices y grado 2n-2) a veces se denominan gráficas de cóctel : son gráficas completas con un conjunto de aristas. haciendo una combinación perfecta eliminada. Familias adicionales de gráficos simétricos con un número par de vértices 2n son los gráficos bipartitos completos divididos uniformemente K n,n y los gráficos de corona en 2n vértices. Muchos otros gráficos simétricos se pueden clasificar como gráficos circulantes (pero no todos).
El gráfico de Rado forma un ejemplo de un gráfico simétrico con infinitos vértices y grados infinitos.
Combinando la condición de simetría con la restricción de que las gráficas sean cúbicas (es decir, todos los vértices tengan grado 3) se obtiene una condición bastante fuerte, y dichas gráficas son lo suficientemente raras como para incluirlas en la lista. Todos ellos 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 años [1] ) el entonces actual censo de Foster (enumerando todos los gráficos simétricos cúbicos hasta 512 vértices) se publicó en forma de libro. [9] Los primeros trece elementos de la lista son gráficos simétricos cúbicos con hasta 30 vértices [10] [11] (diez de ellos también son transitivos por distancia ; las excepciones son las indicadas):
Otras gráficas simétricas cúbicas muy conocidas son la gráfica de Dyck , la gráfica de Foster y la gráfica de Biggs-Smith . Las diez gráficas transitivas de distancia enumeradas anteriormente, junto con la gráfica de Foster y la gráfica de Biggs-Smith , son las únicas gráficas transitivas de distancia cúbicas.
La conectividad de vértices de un gráfico simétrico es siempre igual al grado d . [3] Por el contrario, para gráficos transitivos de vértice en general, la conectividad de vértice está limitada por debajo de 2 ( d + 1)/3. [2]
Una gráfica t -transitiva de grado 3 o más tiene una circunferencia de al menos 2 ( t – 1). Sin embargo, no hay gráficas t -transitivas finitas de grado 3 o más para t ≥ 8. En el caso de que el grado sea exactamente 3 (gráficas simétricas cúbicas), no hay ninguna para t ≥ 6.
