Gráfico simétrico

En el campo matemático de la teoría de grafos , un grafo G es simétrico o transitivo por arcos si, dados cualesquiera dos pares ordenados de vértices adyacentes${\displaystyle (u_{1},v_{1})}$y${\displaystyle (u_{2},v_{2})}$de G , hay un automorfismo

${\displaystyle f:V(G)\rightarrow V(G)}$

de tal manera que

${\ Displaystyle f (u_ {1}) = u_ {2}}$y${\displaystyle f(v_{1})=v_{2}.}$^{[ 1 ]}

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 ]} Dicho grafo también se denomina a veces 1-arco -transitivo ^{[ 2 ]} o flag-transitivo . ^{[ 3 ]}

Por definición (ignorando u ₁ y u ₂ ), un grafo simétrico sin vértices aislados también debe ser transitivo en vértices . ^{[ 1 ]} Dado que la definición anterior mapea una arista a otra, un grafo simétrico también debe ser transitivo en aristas . Sin embargo, un grafo transitivo en aristas no tiene por qué ser simétrico, ya que a—b podría mapearse a c—d , pero no a d—c . Los grafos estrella son un ejemplo sencillo de ser transitivo en aristas sin ser transitivo en vértices ni simétrico. Como ejemplo adicional, los grafos semisimétricos son transitivos en aristas y regulares , pero no transitivos en vértices.

Todo grafo simétrico conexo debe ser transitivo en vértices y transitivo en aristas, y lo contrario es cierto para grafos de grado impar . ^{[ 3 ]} Sin embargo, para grado par , existen grafos conexos que son transitivos en vértices y transitivos en 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 utilizan el término "grafo simétrico" para referirse a un grafo que es transitivo en vértices y transitivo en aristas, en lugar de un grafo transitivo en arcos. Dicha definición incluiría los grafos semitransitivos, que quedan excluidos según la definición anterior.

Un grafo transitivo en 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 abarca dos pares de vértices, cada uno separado por la misma distancia. 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 cualesquiera dos vértices consecutivos en la secuencia son adyacentes, y cualquier vértice repetido está separado por más de 2 pasos. Un grafo t -transitivo es un grafo tal que el grupo de automorfismos actúa transitivamente sobre los t -arcos , pero no sobre los ( t + 1 )-arcos . Dado que los 1-arcos son simplemente aristas, todo grafo simétrico de grado 3 o superior debe ser t -transitivo para algún t , y el valor de t puede utilizarse para clasificar aún más los grafos simétricos. El cubo es 2-transitivo , por ejemplo. ^{[ 1 ]}

Cabe señalar que, convencionalmente, el término "grafo simétrico" no es complementario al término " grafo asimétrico ", ya que este último se refiere a un grafo que no tiene simetrías no triviales.

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 se forman mediante los vértices y 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 lugar a los grafos hipercubo (con 2n ^vértices y grado n). De forma similar, la extensión del octaedro a n dimensiones da lugar a los grafos de los politopos cruzados ; esta familia de grafos (con 2n vértices y grado 2n − 2) a veces se denomina grafos de cóctel : son grafos completos a los que se les ha eliminado un conjunto de aristas que forman un emparejamiento perfecto. 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 (aunque no todos).

El grafo de Rado constituye un ejemplo de grafo simétrico con infinitos vértices y grado infinito.

La conectividad de vértices de un grafo simétrico siempre es igual al grado d . ^{[ 3 ]} En cambio, para los grafos transitivos de vértices en general, la conectividad de vértices está acotada inferiormente por 2( d  + 1)/3. ^{[ 2 ]}

Un grafo t -transitivo de grado 3 o superior tiene una circunferencia de al menos 2( t  − 1). Sin embargo, no existen grafos t -transitivos finitos de grado 3 o superior para t ≥ 8. En el caso de que el grado sea exactamente 3 (grafos cúbicos simétricos), no existen para t ≥ 6.      

• Teoría algebraica de grafos
• Galería de gráficos con nombre
• Mapa regular

• Grafos cúbicos simétricos (The Foster Census) . Archivos de datos para todos los grafos cúbicos simétricos de hasta 768 vértices, y algunos grafos cúbicos de hasta 1000 vértices. Gordon Royle, actualizado en febrero de 2001, consultado el 18 de abril de 2009.
• Grafos simétricos trivalentes (cúbicos) con hasta 10000 vértices . Marston Conder , 2011.