En el campo matemático de la teoría de grafos , un grafo transitivo de aristas es un grafo G tal que, dadas dos aristas e 1 y e 2 de G , existe un automorfismo de G que mapea e 1 a e 2 . [1]
En otras palabras, un grafo es transitivo en sus aristas si su grupo de automorfismos actúa transitivamente en sus aristas.
El número de grafos transitivos de aristas simples conexos en n vértices es 1, 1, 2, 3, 4, 6, 5, 8, 9, 13, 7, 19, 10, 16, 25, 26, 12, 28... (secuencia A095424 en la OEIS )
Los grafos transitivos por aristas incluyen todos los grafos simétricos , como los vértices y las aristas del cubo . [1] Los grafos simétricos también son transitivos por vértices (si son conexos ), pero en general los grafos transitivos por aristas no necesitan ser transitivos por vértices. Todo grafo transitivo por aristas conexo que no sea transitivo por vértices debe ser bipartito , [1] (y por lo tanto puede colorearse con solo dos colores), y semisimétrico o biregular . [2]
Ejemplos de grafos transitivos de arista pero no de vértice incluyen los grafos bipartitos completos donde m ≠ n, que incluyen los grafos en estrella . Para grafos en n vértices, hay (n-1)/2 de tales grafos para n impar y (n-2) para n par. Se pueden formar grafos transitivos de arista adicionales que no son simétricos como subgrafos de estos grafos bipartitos completos en ciertos casos. Los subgrafos de grafos bipartitos completos K m,n existen cuando m y n comparten un factor mayor que 2. Cuando el máximo común divisor es 2, existen subgrafos cuando 2n/m es par o si m=4 y n es un múltiplo impar de 6. [3] Entonces, existen subgrafos transitivos de arista para K 3,6 , K 4,6 y K 5,10 pero no para K 4,10 . Una construcción alternativa para algunos gráficos transitivos de aristas es agregar vértices a los puntos medios de las aristas de un gráfico simétrico con v vértices y e aristas, creando un gráfico bipartito con e vértices de orden 2 y v de orden 2e/v.
Un grafo transitivo por aristas que también es regular , pero que no es transitivo por vértices, se denomina semisimétrico . El grafo de Gray , un grafo cúbico de 54 vértices, es un ejemplo de grafo regular que es transitivo por aristas pero no por vértices. El grafo de Folkman , un grafo cuártico de 20 vértices, es el grafo más pequeño de este tipo.
La conectividad de vértices de un gráfico transitivo de aristas siempre es igual a su grado mínimo . [4]
