En el campo matemático de la teoría de grafos , un gráfico transitivo de aristas es un gráfico G tal que, dadas dos aristas cualesquiera e 1 y e 2 de G , existe un automorfismo de G que asigna e 1 a e 2 . [1]
En otras palabras, un gráfico es transitivo de aristas si su grupo de automorfismo actúa transitivamente en sus aristas.
El número de gráficos transitivos de aristas simples conectados 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 gráficos transitivos de aristas incluyen todos los gráficos simétricos , como los vértices y las aristas del cubo . [1] Los gráficos simétricos también son transitivos por vértices (si están conectados ), pero en general los gráficos transitivos por bordes no necesitan ser transitivos por vértices. Todo gráfico transitivo de aristas conectado que no sea transitivo de vértices debe ser bipartito , [1] (y por lo tanto puede colorearse con solo dos colores) y semisimétrico o biregular . [2]
Ejemplos de gráficos transitivos de aristas pero no de vértices incluyen los gráficos bipartitos completos donde m ≠ n, que incluyen los gráficos de estrellas . Para gráficas en n vértices, hay (n-1)/2 gráficas para n impares y (n-2) para n pares. En ciertos casos, se pueden formar gráficos transitivos de aristas adicionales que no son simétricos como subgrafos de estos gráficos bipartitos completos. Los subgrafos de grafos bipartitos completos K m,n existen cuando myn comparten un factor mayor que 2. Cuando el máximo común divisor es 2, los subgrafos existen cuando 2n/m es par o si m=4 y n es un múltiplo impar de 6 [3] Entonces existen subgrafos transitivos de borde 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 gráfico transitivo de aristas que también es regular , pero aún no transitivo de vértices, se llama semisimétrico . El gráfico de Gray , un gráfico cúbico de 54 vértices, es un ejemplo de un gráfico regular que es transitivo de aristas pero no transitivo de vértices. El gráfico de Folkman , un gráfico cuártico de 20 vértices, es el gráfico 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]
