# Archives

## A cubic graph with cubic diameter

Submitted by stannic on Mon, 03/06/2017 - 03:53.The Fifteen puzzle is sometimes generalized to a sliding puzzle on an arbitrary simple connected graph *G* with *n* vertices in the following way. *n* − 1*n* − 1)*G*. At most one piece is placed on each vertex. One vertex of *G* is left unoccupied. A move consists in choosing a vertex *v* adjacent to the currently unoccupied vertex *v*_{0} and 'sliding' the piece at *v* along the edge (*v*; *v*_{0}). The aim is to restore the order so that piece numbered *i* occupies vertex numbered *i*, for *i* = 1 .. *n* − 1*G* is the

» 4 comments | read more