Grafo de Cayley

O grafo de Cayley do grupo livre em dois geradores a e b
Famílias de grafos definidos por seus automorfismos
distância-transitivodistância-regularfortemente regular
simétrico (arco-transitivo)t-transitivo, t ≥ 2.

(se conectado)
transitivo nos vértices e nas arestasaresta-transitivo e regulararesta-transitivo
vértice-transitivoregular
grafo de Cayleyantissimétricoassimétrico

Em matemática, área da teoria dos grafos, um grafo de Cayley, também conhecido como grafo colorido de Cayley, diagrama de Cayley, diagrama de grupo, ou grupo colorido é um grafo que codifica a estrutura abstrata de um grupo. Sua definição é sugerida pelo teorema de Cayley (nomeado em honra a Arthur Cayley) e usa um conjunto de geradores específico, usualmente finito, para o grupo. É um instrumento central em combinatória e teoria geométrica de grupos.

Definição

Suponha que seja um grupo e seja um conjunto de geradores. O grafo de Cayley é um grafo direcionado colorido construído como se segue

Na teoria geométrica de grupos, o conjunto é geralmente assumido ser finito, simétrico, isto é e não contendo o elemento identidade do grupo. Neste caso, o grafo de Cayley incolor é um grafo comum: suas arestas não são orientadas e não contém laços se e somente se

Exemplos

O grafo de Cayley do grupo diedro D4 em dois geradores α e β

Ver também