Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Cayley graph
Summary
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley), and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing families of expander graphs.
Let be a group and be a generating set of . The Cayley graph is an edge-colored directed graph constructed as follows:
Each element of is assigned a vertex: the vertex set of is identified with
Each element of is assigned a color .
For every and , there is a directed edge of color from the vertex corresponding to to the one corresponding to .
Not every source requires that generate the group. If is not a generating set for , then is disconnected and each connected component represents a coset of the subgroup generated by .
If an element of is its own inverse, then it is typically represented by an undirected edge.
The set is sometimes assumed to be symmetric (i.e. ) and not containing the identity element of the group. In this case, the uncolored Cayley graph can be represented as a simple undirected graph.
In geometric group theory, the set is often assumed to be finite which corresponds to being locally finite.
Suppose that is the infinite cyclic group and the set consists of the standard generator 1 and its inverse (−1 in the additive notation); then the Cayley graph is an infinite path.
Similarly, if is the finite cyclic group of order and the set consists of two elements, the standard generator of and its inverse, then the Cayley graph is the cycle . More generally, the Cayley graphs of finite cyclic groups are exactly the circulant graphs.
The Cayley graph of the direct product of groups (with the cartesian product of generating sets as a generating set) is the cartesian product of the corresponding Cayley graphs.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.