Grafo de Cayley

Su nombre honra al matemático británico Arthur Cayley, quien introdujo estos grafos en 1878.

cumple: El segundo punto es en ocasiones cambiado por lo siguiente: el par ordenado (g,h) es una arista del grafo si existe s perteneciente a S tal que sg=h (o, de forma equivalente, si hg-1 pertenece a S).

En general se estudia el grafo de Cayley con S generador del grupo G (lo que hace al grafo conexo) y tal que el neutro del grupo no está en S (de esta manera no hay lazos en el grafo).

Además, suele asumirse que el conjunto S es simétrico, es decir, si t pertenece a S entonces t-1 también.

Esta última propiedad hace al grafo de Cayley no orientado.

Grafo de Cayley del grupo libre de dos generadores, a y b .
Grafo de Cayley de S 3 con conjunto de generadores {(12), (23), (13)}
Grafo de Cayley del grupo S3 con conjunto de generadores {(12), (123)}