Cayley graph Cay(G,S): vertices = elements of group G, edge from g to gs for each generator s∈S. Always vertex-transitive (G acts on itself by left multiplication). Fundamental bridge between group theory and graph theory.
How to Use
Select group:
- G: Finite group
- S: Generators
- Graph: Cayley graph
Classic Examples
Cay(Z_n, {1}): cycle C_n. Cay(Z_n, {1,-1}): cycle with bidirected edges. Cay(Z_2^n, {e_i}): hypercube Q_n. Cay(S_n, transpositions): various beautiful graphs. Group structure ↔ graph properties.
Applications
Network design: Cayley graphs as interconnection networks (hypercubes, butterfly). Expander graphs: Cayley graphs of certain groups. Cryptography: hash functions based on Cayley graphs. Coding theory: Cayley graph codes.
Step-by-Step Instructions
- 1Select group G.
- 2Choose generators S.
- 3Build Cayley graph.
- 4Analyze properties.
- 5Compute diameter.