A notion introduced by R. M. Wilson in 1974. Given a finite graph G with n vertices, puz(G) is defined as the graph whose nodes are the labelings of G leaving one node unoccupied, i.e., the ways to place n - 1 different counters on n - 1 nodes of G. This labelings can be identified with the permutations of {0, 1, 2, ..., n - 1}, so that puz(G) has n! nodes. Two labelings are connected by an edge in puz(G) iff one can be transformed into the other by moving one of the labels along one edge of G. The possible labelings of two vertices of the path graph P_3 are illustrated above, giving puz(P_3) as illustrated.

15 puzzle | graph | Hanoi graph | permutation | tower of Hanoi