Cayley Graph - Elementary Properties

Elementary Properties

• If a member of the generating set is its own inverse, then it is generally represented by an undirected edge.

• The Cayley graph depends in an essential way on the choice of the set of generators. For example, if the generating set has elements then each vertex of the Cayley graph has incoming and outgoing directed edges. In the case of a symmetric generating set with elements, the Cayley graph is a regular graph of degree

• Cycles (or closed walks) in the Cayley graph indicate relations between the elements of In the more elaborate construction of the Cayley complex of a group, closed paths corresponding to relations are "filled in" by polygons. This means that the problem of constructing the Cayley graph of a given presentation is equivalent to solving the Word Problem for .

• If is a surjective group homomorphism and the images of the elements of the generating set for are distinct, then it induces a covering of graphs

where

In particular, if a group has generators, all of order different from 2, and the set consists of these generators together with their inverses, then the Cayley graph is covered by the infinite regular tree of degree corresponding to the free group on the same set of generators.

• A graph can be constructed even if the set does not generate the group However, it is disconnected and is not considered to be a Cayley graph. In this case, each connected component of the graph represents a coset of the subgroup generated by .

• For any finite Cayley graph, considered as undirected, the vertex connectivity is at least equal to 2/3 of the degree of the graph. If the generating set is minimal (removal of any element and, if present, its inverse from the generating set leaves a set which is not generating), the vertex connectivity is equal to the degree. The edge connectivity is in all cases equal to the degree.