En el campo matemático de la teoría de grafos , un grafo transitivo de aristas es un grafo G tal que, dadas cualesquiera dos aristas e 1 y e 2 de G , hay un automorfismo de G que mapea e 1 a e 2 . [1]
Familias de gráficos definidas por sus automorfismos | ||||
---|---|---|---|---|
distancia-transitiva | → | distancia regular | ← | muy regular |
↓ | ||||
simétrico (arco-transitivo) | ← | t -transitivo, t ≥ 2 | simétrico sesgado | |
↓ | ||||
(si está conectado) vértice y borde transitivo | → | edge-transititive y regular | → | borde transitivo |
↓ | ↓ | ↓ | ||
vértice-transitivo | → | regular | → | (si es bipartito) birregular |
↑ | ||||
Gráfico de Cayley | ← | simétrico cero | asimétrico |
En otras palabras, un gráfico es transitivo por los bordes si su grupo de automorfismo actúa de manera transitiva en sus bordes.
Ejemplos y propiedades
Los gráficos de borde transitivo incluyen cualquier gráfico bipartito completo y cualquier gráfico simétrico , como los vértices y las aristas del cubo . [1] Los gráficos simétricos también son transitivos de vértice (si están conectados ), pero en general los gráficos de borde transitivo no necesitan ser transitivos de vértice. El gráfico de Gray es un ejemplo de un gráfico que es transitivo por aristas pero no transitivo por vértices. Todos estos gráficos son bipartitos , [1] y, por lo tanto, se pueden colorear con solo dos colores.
Un gráfico de borde transitivo que también es regular , pero no de vértice transitivo, se llama semi-simétrico . El gráfico de Gray nuevamente proporciona un ejemplo. Todo gráfico de borde transitivo que no sea de vértice transitivo debe ser bipartito y semi-simétrico o birregular . [2]
La conectividad de vértice de un gráfico de borde transitivo siempre es igual a su grado mínimo . [3]
Marston Conder ha compilado una lista completa de todos los gráficos transitivos de bordes conectados en hasta 47 vértices y una lista completa de todos los gráficos bipartitos de bordes transitivos conectados en hasta 63 vértices .
Ver también
- Edge-transititive (en geometría)
Referencias
- ↑ a b c Biggs, Norman (1993). Teoría de grafos algebraicos (2ª ed.). Cambridge: Cambridge University Press. pag. 118. ISBN 0-521-45897-8.
- ^ Lauri, Josef; Scapellato, Raffaele (2003), Temas de Automorfismos Gráficos y Reconstrucción , Textos de Estudiantes de la Sociedad Matemática de Londres, Cambridge University Press, págs. 20–21, ISBN 9780521529037.
- ^ Watkins, Mark E. (1970), "Conectividad de gráficos transitivos", Journal of Combinatorial Theory , 8 : 23-29, doi : 10.1016 / S0021-9800 (70) 80005-9 , MR 0266804
enlaces externos
- Weisstein, Eric W. "Gráfico de borde transitivo" . MathWorld .