Cayley graph: one construct, many systems

A Cayley graph pictures a group as a network: each group element is a vertex, and an edge joins two elements whenever one is obtained from the other by applying a chosen generator, so the graph encodes the group's multiplication relative to that generating set. Budden's The fascination of groups introduces such group graphs, and Godsil and Royle's Algebraic graph theory treats their properties formally. The referent is the generator-edge network of a group, the same object that, for the symmetric group, underlies the paths a band of ringers can trace.[1][2]

Unit

A vertex-and-edge graph on a group's elements

Recovery means

Not applicable

Measured by

Characterised by vertex-transitivity, connectivity, girth, and Hamiltonicity

Change ringing realises exactly this object: the rows are the vertices and the permitted neighbour-swaps between consecutive rows are the generator-edges, so a method that rings every row once and returns to rounds is a Hamiltonian cycle on the Cayley graph of the symmetric group. White's Ringing the cosets and Treble dodging minor methods analyse whole classes of methods as such closed walks across cosets of the graph. It is the identical construct as the algebraist's group graph, here walked out physically in a tower rather than drawn on paper.[3][4]

Unit

A Hamiltonian cycle on the Cayley graph of Sₙ

Recovery means

Not applicable

Measured by

Assessed by whether a walk visits every row once and closes to rounds